GCD (najveći zajednički djeljitelj)

GCD je najveći broj s kojim su dva zadana cijela broja djeljiva. Za njegovo nalaženje koristimo Euklidov algoritam. Jedna od priktičnih primjena je skraćivanje razlomaka.

Neke implementacije:

Brute force

int gcd(int a, int b) {
  int sol = 1;
  for (int x = 2; x <= a && x <= b; ++x)
    if (a % x == 0 && b % x == 0)
      sol = x;
  return sol;
}

Euklidov algoritam

int gcd(int a, int b) {
  while (b) {
    if (a >= b) {
      a = a % b;
    } else {
      int tmp = b;
      b = a;
      a = tmp;
    }
  }
  return a;
}

Krata i najčešće korištena implementacija

int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

LCM (najmanji zajednički višekratnik)

Najmanji zajednički višekratnik od a i b je najmanji cijeli broj l takav da je djeljiv sa a i sa b. LCM usko povezan s GCD-om.
Naime,

Najmanji zajednički višekratnik

int lcm(int a, int b) {
  return a * (b / gcd(a, b));
}

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License