Algorytm znajdowanie największego wspólnego dzielnika, to taki algorytm, który powinien znać i umieć napisać każdy miłośnik i profesjonalista programowania. Algorytm opisany był w internecie na tysiącu stronach ale od dzisiaj będzie na tysiącu i jednej, włąsnie na tej -1001 
Np:
en.wikipedia.org/wiki/Euclidean_algorithm
en.wikipedia.org/wiki/Binary_GCD_algorithm
Mimo, że niektóre języki programowania mają zaimplementowany ten algorytm to warto go umieć "zrobić" samemu z zawiązanymi oczyma i rękoma i po obudzeniu o północy z głębokiego snu.
haskell ma i gcd i lcm [najwększa wspólna wielokrotność]
python - po zaimportowaniu modułu fractions, też ma.
A co z C/C++? Po #include Więc o co ten cały zgiełk? Już piszę. Tak, wygląda u mnie szblon funkcji, w pliku stl_algo.h:
[bbone=cpp,2277]/**
* This is a helper function for the rotate algorithm specialized on RAIs.
* It returns the greatest common divisor of two integer values.
*/
template
_EuclideanRingElement
_gcd(EuclideanRingElement __m, _EuclideanRingElement __n)
{
while (__n != 0)
{
_EuclideanRingElement __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}[/bbone]
Możemy napisać malutki programik do testowania, np:
[bbone=cpp,2278]#include
use namespace std;
int main(){
int a, b;
while (cin >> a >> b)
cout << __gcd(a, b) << endl;
}[/bbone]
I potestować dla zestawu różnych liczb oraz kombinacji liczb i zera - jest ok, u mnie jest
Teraz potestujmy dla liczb np
-312 213
-312 -213
312 -213 .... itd
U mnie już nie ok, ale patrząc na kod i wiedząc jak c/c++ liczy '%' nic dziwnego, u Ciebie tak samo?
To samo można zrobić dla pythona [nie ok], haskell [w haskellu jest ok] i innych języków z wbudowaną tą funkcją.
[color=#0000FF]WNIOSEK[/color]
Trzeba uważać co się robi i się zabezpieczać.!
I jeszcze trzeba pamiętać, że [color=#0000BF]__gcd()[/color] to nie standart c++ i jest w kompilatorze gcc ale w innych kompilatorach może być inaczej.
¹ notatka o #include
