Евклидовый алгоритм / GCD в Python ⇐ Python

[Anonymous]

Я пытаюсь написать евклидовый алгоритм в Python. Это найти GCD двух действительно больших чисел. Формула - это a = bq + r, где a и b - два числа, q - это количество раз, что B делит равномерно, а R - остаток. < /p>

Я могу написать код, чтобы найти это, однако, если исходные числа не дают оставшегося (r) нуля, то алгоритм переходит к шагу 2 => b = rx + y. (То же самое, что и первый шаг, но просто подбадривать b для a и r для b) два шага повторяются, пока r не разделит как A, так и B равномерно. < /p>

Это мой код Я еще не понял, как сделать подборы значений и создать цикл, пока не найден GCD. < /P>

a = int(input("What's the first number? "))
b = int(input("What's the second number? "))
r = int(a - (b)*int(a/b))

if r == 0:
print("The GCD of the two choosen numbers is " + str(b))

elif r != 0:
return b and r
(b == a) and (r == b)

print("The GCD of the two numbers is " + str(r))


Подробнее здесь: https://stackoverflow.com/questions/216 ... -in-python