Euklides algoritm
From Wikipedia, the free encyclopedia
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]
- Två heltal a och b, där a > b är givna.
- Om b = 0 är algoritmen klar och svaret är a.
- I annat fall beräknas c, resten när man delat a med b.
- 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).