Алгоритм нахождения НОД вычитанием
Из большего числа вычитаем меньшее.
Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6
a = 50
b = 130
while a != b:
if a > b:
a = a - b
else:
b = b - a
print(a)
Функция вычисления НОД
def gcd(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
print(a)
Блок-схема алгоритма Евклида
Примечание. В модуле math языка программирования Python есть функция gcd(), вычисляющая наибольший общий делитель двух чисел.
>>> import math
>>> math.gcd(30, 18)
6
Перебор делителей – это алгоритм, применяемый для определения, является ли натуральное число простым, или оно является сложным, то есть составным.
Простые числа - это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.
Алгоритм перебора делителей заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню из тестируемого числа.
Если хотя бы один делитель делит исследуемое число без остатка, то это число является составным. Если ни одного такого делителя не находится, то число признается простым.
import math
n = int(input())
Достарыңызбен бөлісу: |
