для нахождения НОДа не мало, не буду углубляться во всякие сложные алгоритмы, так как вряд ли Вы их проходите.
Сравним перебор и алгоритм Евклида, сразу можем сказать, что алгоритм Евклида в разы быстрее, так как при переборе мы тупо перебираем значения, то есть, данный алгоритм зависит от величины числа очень сильно. Конечно, алгоритм Евклида также зависит от введенного числа, однако, в нём будет намного меньше повторений, нежели в с перебором.
Можем глянуть немного статистики:
Генерируется 500 пар чисел
Перебор - 0.5022 с
Алгоритм Евклида - 0.0008
Теперь мы точно можем сделать вывод, что алгоритм Евклида в разы быстрее простого перебора.
Python
Объяснение:
код:
import random
n = random.randint(10, 100)
t = []
p = []
for i in range(1, n):
if n % i == 0:
i = str(i)
t += i
i = int(i)
for k in range(2, i):
if i % k == 0:
i = str(i)
p += i
break
t = list(map(int, t))
p = list(map(int, p))
for x in p:
if x in t:
t.remove(x)
t.remove(1)
if len(t) == 0:
t.append(n)
print(*t)
else:
s = [str(x) for x in t]
print('simple', '(', n, ')', '=', *s)
Начало
Ввод x
x < 2 под ДА внести y := x+6, под НЕТ внести y:=x*x+6
Вывод y
Конец
Объяснение: