Алгоритм Евклида — различия между версиями

Текущая версия на 16:47, 23 октября 2008

Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД, в англоязычной литературе - GCD - Greatest Common Divisor) двух целых чисел. Для упрощения, ниже будем считать, что .

Реализация на языке Python и пример выполнения:

 def gcd(a, b):
    print a,b
    if a == 0:
            return b
    return gcd(b % a, a)

Calculating gcd( 123456 , 6122256 ):
123456 6122256
72912 123456
50544 72912
22368 50544
5808 22368
4944 5808
864 4944
624 864
240 624
144 240
96 144
48 96
0 48
gcd( 123456 , 6122256 )= 48

Время работы алгоритма Евклида составляет O(log a +log b) арифметических операций над натуральными числами.