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:
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; }
int gcd(int a, int b) { while (b) { if (a >= b) { a = a % b; } else { int tmp = b; b = a; a = tmp; } } return a; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
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,
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