Euklides algoritm

Euklides algoritm är en algoritm för att bestämma största gemensamma delare till två heltal[1]. Det är en av de äldsta kända algoritmerna och beskrivs i Euklides Elementa.[2] Algoritmen kräver inte att man kan dela upp talen i faktorer.

Algoritmen kan beskrivas på följande sätt:[1]

  1. Två heltal a och b, där a > b är givna.
  2. Om b = 0 är algoritmen klar och svaret är a.
  3. I annat fall beräknas c, resten när man delat a med b.
  4. sätt a = b, b = c och börja om från steg 2 igen, (a får det värde b har och b får det värde c har).
  1. ^ [a b] ”Euklides algoritm”. Nationalencyklopedin. http://www.ne.se/uppslagsverk/encyklopedi/lång/euklides-algoritm. Läst 3 september 2016. 
  2. ^ För rationella tal i bok VII, för reella tal i bok X. Se Weisstein, Eric W., "Euclidean Algorithm", MathWorld. (engelska)

From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by razib.in