Euklids algoritme
Fra Wikipedia, den frie encyklopedi
Euklids algoritme er en rask algoritme for å beregne største felles faktor (gcd) til to heltall.
[rediger] Beskrivelse av algoritmen
Gitt to heltall, a og b, finn minste heltall d slik at d deler a og b. Hvis b = 0, returner a. Ellers gjentas prosessen med tallene b og a modulo b. Det er også mulig å bruke gjentatt subtraksjon, der det minste tallet trekkes fra det største, helt til ett av tallene er 0. Dette er den opprinnelige algoritmen, men den er mindre effektiv.
[rediger] Implementering
I blant annet C++ og Java ser algoritmen slik ut:
int gcd(int a,int b){
if ( b == 0 )
return a;
return gcd(b,a%b);
}
[rediger] Eksempel
Finn største felles faktor til 42 og 24.
a = 42, b = 24
a = 24, b = (42 mod 24) = 18
a = 18, b = (24 mod 18) = 6
a = 6, b = (18 mod 6) = 0
b = 0, så svaret er a = 6
