Keskustelu: Ohjelmointikysymykset: C, QB, VB6: Suurin yhteinen tekijä

Miten etsitään suurimman yhteisen tekijän. esim. murtolukujen 4/8 suurin yhteinen tekijä on 4 (1/2)

google: "suurin yhteinen tekijä"
=> toinen tulos: http://fi.wikipedia.org/wiki/Eukleideen_algoritmi

Dim T1
Dim T2
T2 = 32
T1 = 24

For i = T2 To 0 Step -1
DoEvents
    For a = 0 To T2
    DoEvents
        For u = 0 To T1
            If i * a = T2 And i * u = T1 Then
            MsgBox i
            Exit Sub
            End If
        Next u
    Next a
Next i

Ei nyt mikään älyttömän hyvä koodi, mut toimii ainaki pienemmillä luvuilla...

Hajotat ne ensin tekijöihin ja sitten vertailet. Eli vähemmän mukaan aina. Vaikkapa 72 ja 162, tekijöiksi tulee 2^3*3^2 ja 2*3^3, ja näistä otetaan siis yksi kakkonen ja kaksi kolmosta, yhteensä 18. Lopputuloksena on 4*18 ja 9*18.

Toisaalta voit hajottaa niitä yhtä aikaa (olisiko tuo ylläoleva juuri se, en jaksa katsoa :) Eli jos molemmat ovat jaollisia a:lla, kerrotaan tekijä ja jaetaan molemmat luvut a:lla.

Kannattaa todellakin tutustua tuohon Eukleideen algoritmiin (Euclidean algorithm), sillä se on isoillakin luvuilla nopea ja hyvinkin yksinkertainen toteuttaa.
Perässä englanninkielisestä wikipediasta kopioidut toteutukset C/C++:lle sekä rekursiivisena, että iteratiivisena toteutuksena.

int gcd(int a, int b) {
  if (b == 0)
    return a;

  return gcd(b, a % b);
}

int gcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

Suurinta yhteistä tekijää etsitään jakolaskun avulla. Edellisen laskun jakaja on seuraavan jaettava, ja edellisen laskun jakojäännös on seuraavan jakaja. Laskemista jatketaan, kunnes jakojäännös on 0. Suurin yhteinen tekijä on sen laskun jakaja. Esim. tutkitaan lukuja 30 ja 16.

30 / 16 = 1, jää 14
16 / 14 = 1, jää 2
14 / 2 = 7, jää 0

Nyt tiedetään, että suurin yhteinen tekijä on 2.

Teinpä vielä esimerkin QBasicille.

' palauttaa lukujen suurimman yhteisen tekijän
FUNCTION SYT% (A%, B%)
   WHILE B% <> 0
      U% = B%
      B% = A% MOD B%
      A% = U%
   WEND
   SYT% = A%
END FUNCTION

INPUT "Kirjoita osoittaja: ", o%
INPUT "Kirjoita nimittäjä: ", n%

j% = SYT%((o%), (n%))

PRINT
PRINT o%; "/"; n%; "="; o% / j%; "/"; n% / j%