Question

Как можно найти НОД двух натуральных чисел не используя алгоритм евклида? какой метод лучше? Сравните этот алгоритм с алгоритмом евклида. ​

Answer 1

Способов для нахождения НОДа не мало, не буду углубляться во всякие сложные алгоритмы, так как вряд ли Вы их проходите.

Сравним перебор и алгоритм Евклида, сразу можем сказать, что алгоритм Евклида в разы быстрее, так как при переборе мы тупо перебираем значения, то есть, данный алгоритм зависит от величины числа очень сильно. Конечно, алгоритм Евклида также зависит от введенного числа, однако, в нём будет намного меньше повторений, нежели в способе с перебором.

Можем глянуть немного статистики:

Генерируется 500 пар чисел

Перебор - 0.5022 с

Алгоритм Евклида - 0.0008

Теперь мы точно можем сделать вывод, что алгоритм Евклида в разы быстрее простого перебора.

Answer 2

Відповідь:

#НОД чисел 45 и 105

a = 45;

b = 105;

result = False;

if (a > b):

   big = a;

else:

   big = b;

   

i = 2;

while (i <= big):

   if ((a % i == 0) and (b % i == 0)):

       result = i;

   i += 1;

print (result);

Пояснення: