Алгоритм нахождения НОД вычитанием

1. 
   Из большего числа вычитаем меньшее.
   
2. 
   Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
   
3. 
   Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
   
4. 
   Переходим к пункту 1.
   

a = 50

 

while a != b:

a = a - b

b = b - a

 

print(a)

Функция вычисления НОД

def gcd(a, b):

while a != b:

if a > b:

a = a - b

b = b - a

>>> import math

>>> math.gcd(30, 18)

6

Перебор делителей – это алгоритм, применяемый для определения, является ли натуральное число простым, или оно является сложным, то есть составным.

Алгоритм перебора делителей заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню из тестируемого числа.

Если хотя бы один делитель делит исследуемое число без остатка, то это число является составным. Если ни одного такого делителя не находится, то число признается простым.

import math

n = int(input())