Найти площадь и периметр прямоугольного треугольника по двум заданным катетам


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



бет19/34
Дата05.01.2022
өлшемі186,75 Kb.
#129167
1   ...   15   16   17   18   19   20   21   22   ...   34
Байланысты:
шпор

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

  1. Из большего числа вычитаем меньшее.

  2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).

  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

  4. Переходим к пункту 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())



 



Достарыңызбен бөлісу:
1   ...   15   16   17   18   19   20   21   22   ...   34




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет