Как найти наибольший делитель числа пайтон - Сайт, где вы сможете решить свои вопросы

НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(HCF).

Например, HCF / GCD двух чисел 54 и 24 равен 6. Поскольку 6 – это наибольший общий делитель, который полностью делит 54 и 24.

Разберемся как найти НОД двух чисел в Python.

НОД с использованием функции gcd()

gcd() в python – это встроенная функция, предлагаемая математическим модулем для поиска наибольшего общего делителя двух чисел.

Синтаксис:

 
gcd(a, b)

Где a и b – два целых числа, которые передаются в качестве аргумента функции gcd().

Давайте создадим программу для печати НОД двух чисел, используя встроенную функцию math.gcd() в python.

math_fun.py

 
# create a program to print the gcd of two number in python using the math.gcd() function. 
import math 
print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number 
print(" GCD of two number 0 and 48 is ", math.gcd(0, 48)) 
a = 60 # assign the number to variable a 
b = 48 # assign the number to variable b 
print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function. 
print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number 
print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18)) 
print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48))

Выход:

В приведенном выше примере функция math.gcd() генерирует НОД двух заданных чисел. В функции gcd() a и b передаются в качестве аргумента, который возвращает наибольший общий делитель двух целых чисел, полностью разделяя числа.

НОД с использованием рекурсии

Рекурсия – это функция, потребляющая память, определенная в Python, которая вызывает себя через самореферентное выражение. Это означает, что функция будет постоянно вызывать и повторять себя до тех пор, пока не будет выполнено определенное условие для возврата наибольшего общего делителя числа.

Псевдокод алгоритма

Шаг 1: Возьмите два входа, x и y, от пользователя.

Шаг 2: Передайте входной номер в качестве аргумента рекурсивной функции.

Шаг 3: Если второе число равно нулю(0), возвращается первое число.

Шаг 4: В противном случае он рекурсивно вызывает функцию со вторым числом в качестве аргумента, пока не получит остаток, который делит второе число на первое число.

Шаг 5: Вызовите или назначьте gcd_fun() переменной.

Шаг 6: Отобразите НОД двух чисел.

Шаг 7: Выйдите из программы.

Разберемся с программой для нахождения НОД двух чисел с помощью рекурсии.

gcdRecur.py

 
# write a program to understand the GCD of two number in python using the recursion. 
def gcd_fun(x, y): 
    if(y == 0): # it divide every number 
        return x  # return x 
    else: 
        return gcd_fun(y, x % y) 
x =int(input("Enter the first number: ")) # take first no.  
y =int(input("Enter the second number: ")) # take second no.  
num = gcd_fun(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num

Выход:

Нахождение НОД с помощью цикла

Давайте создадим программу для нахождения НОД двух чисел в Python с помощью циклов.

gcdFile.py

 
def GCD_Loop( a, b): 
    if a > b:  # define the if condition 
        temp = b 
    else: 
        temp = a 
    for i in range(1, temp + 1): 
        if(( a % i == 0) and(b % i == 0 )): 
            gcd = i 
    return gcd 
x = int(input(" Enter the first number: ") ) # take first no.  
y =int(input(" Enter the second number: ")) # take second no.  
num = GCD_Loop(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num

Выход:

Как мы видим в приведенной выше программе, мы берем два значения в качестве входных и передаем эти числа в функцию GCD_Loop(), чтобы вернуть GCD.

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

Алгоритм Евклида – эффективный метод нахождения наибольшего общего делителя двух чисел. Это самый старый алгоритм, который делит большее число на меньшее и берет остаток. Опять же, он делит меньшее число от остатка, и этот алгоритм непрерывно делит число, пока остаток не станет 0.

Например, предположим, что мы хотим вычислить HCF двух чисел, 60 и 48. Затем мы делим 60 на 48; он возвращает остаток 12. Теперь мы снова делим число 24 на 12, а затем он возвращает остаток 0. Таким образом, мы получаем HCF равным 12.

Псевдокод алгоритма Евклида

Шаг 1: Есть два целых числа, например a и b.

Шаг 2: Если a = 0, то НОД(a, b) равен b.

Шаг 3: Если b = 0, НОД(a, b) равен a.

Шаг 4: Найти mod b.

Шаг 5: Предположим, что a = b и b = R.

Шаг 6: Повторяйте шаги 4 и 3, пока mod b не станет равным или большим 0.

Шаг 7: GCD = b и затем распечатайте результат.

Шаг 8: Остановите программу.

Найдем HCF или GCD двух чисел, используя алгоритм Евклида в python.

Euclid.py

 
# Create a program to find the GCD of two number in python using the Euclid's Algorithm. 
def find_hcf(a,b): 
    while(b): 
        a, a = b, a % b 
        return a 
a = int(input(" Enter the first number: ") ) # take first no.  
b = int(input(" Enter the second number: ")) # take second no.  
num = find_hcf(a, b) # call the find_hcf() to get the result 
print("  The HCF of two number a and b is ") 
print(num) # call num

Выход:

Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.

Источник

Делитель — это число, на которое нацело делится делимое. У делимого может быть один или несколько делителей, найти их все можно с помощью простого алгоритма, который без проблем реализуется на Python 3.

Нахождение делителей числа

С практической точки зрения будет полезно, если программа на Python не только будет находить делители числа, искать их сумму, определять минимальный и максимальный, а также простые делители.

Каждая подзадача так или иначе связана с предыдущей, поэтому код последующей программы — это немного модернизированный код предыдущей. Кроме того, весь функционал при необходимости можно объединить в одной программе.

Алгоритм нахождения очень простой. В цикле перебираются значения от делимого минус единица до двух включительно. Если делимое нацело делится на текущее значение, то оно является делителем.

Пользователь вводит целое число, делителей которого будет искать программа, тогда код выглядит так:

numb = int(input("Введите целое число: "))
print("Результат:", end = " ")
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        print(i, end = " ")

Например, пользователь ввёл число 625. Программа начинает цикл со значения 624, в цикле проверяется, делится ли нацело 625 на 624, затем цикл переходит на следующую итерацию и работает уже с числом 623 и так до двух. Таким образом, вывод программы будет следующим:

Введите целое число: 625
Результат: 125 25 5

Простые делители числа

Простой делитель — это делитель, который делится только на единицу и самого себя. Для нахождения простых делителей с помощью Python нужно немного модернизировать программу, добавив в неё дополнительный цикл for и переменную счётчик.

Программа построена по следующему алгоритму:

Обнулить счётчик.
В цикле искать делители.
Если найден, искать во вложенном цикле его делители. Это для того, чтобы определить: является ли он простым.
Если найден, увеличить счётчик.
Если счётчик равен нулю, то число простое и надо вывести значение делителя в консоль.
Перейти на следующую итерацию внешнего цикла.

Цикл теперь выглядит так:

numb = int(input("Введите целое число: "))
print("Простые:", end = " ")
for i in range(numb - 1, 1, -1):
    is_simple = 0 # Счётчик
    if (numb % i == 0):
        for j in range(i - 1, 1, -1):
            if (i % j == 0):
                is_simple = is_simple + 1 # Увеличиваем, если находим делитель
        if (is_simple == 0): # Если делителей не было найдено, выводим
            print(i, end = " ")

Понятно, что если значение счётчика больше нуля — то число точно не простое. Можно оптимизировать немного код и сразу завершать вложенный цикл после увеличения счётчика. Для этого можно воспользоваться оператором break в условном операторе, находящемся во вложенном цикле.

Результат работы программы:

Введите целое число: 63
Простые: 7 3

Делители расположены в порядке убывания. И если надо вывести только самый большой простой делитель с помощью Python, то можно после того, как выведется первое число, воспользоваться оператором break для выхода из цикла.

Сумма делителей

Для того чтобы найти сумму всех делителей числа с помощью Python, достаточно добавить в начальную программу переменную, к которой в цикле будет прибавляться каждый найденный делитель.

Код программы:

numb = int(input("Введите целое число: "))
sum_of_dividers = 0
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        sum_of_dividers += i
print("Сумма:", sum_of_dividers)

Результат выполнения кода:

Введите целое число: 63
Сумма: 40

Количество делителей

Этот вариант программы также лишь незначительно отличается от изначального. Для подсчёта делителей нужно ввести переменную-счётчик, к которой будет прибавляться единица каждый раз, когда условие «numb % i == 0» будет выполняться.

numb = int(input("Введите целое число: "))
count_of_dividers = 0
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        count_of_dividers += 1
print("Количество равно:", count_of_dividers)

Результаты выполнения программы:

Введите целое число: 63
Количество равно: 4

Максимальный и минимальный делитель

Для нахождения минимального и максимального делителя в код на Python нужно добавить две переменные: min_divider и max_divider. В цикле делитель будет сравниваться со значением этих переменных и, если необходимо, записываться в них.

Код программы:

numb = int(input("Введите целое число: "))
min_divider = numb
max_divider = 1
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        if (min_divider > i):
            min_divider = i
        if (max_divider < i):
            max_divider = i
print("Минимальный равен:", min_divider)
print("Максимальный равен:", max_divider)

Результат выполнения:

Введите целое число: 63
Минимальный равен: 3
Максимальный равен: 21

Нахождение наименьшего и наибольшего делителя, подсчёт суммы делителей и их количества можно объединить в одну программу на Python. Это не должно вызвать каких-либо проблем или конфликтов, потому что программа работает с 4 независимыми переменными.

Источник

The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.

One way to find the GCD of two numbers is Euclid’s algorithm, which is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.

Write a function called gcd that takes parameters a and b and returns their greatest common divisor.

sampathsris

21.4k11 gold badges69 silver badges98 bronze badges

asked Jun 24, 2012 at 5:13

It’s in the standard library.

>>> from fractions import gcd
>>> gcd(20,8)
4

Source code from the inspect module in Python 2.7:

>>> print inspect.getsource(gcd)
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

As of Python 3.5, gcd is in the math module; the one in fractions is deprecated. Moreover, inspect.getsource no longer returns explanatory source code for either method.

answered Jun 24, 2012 at 5:19

user545424user545424

15.6k11 gold badges57 silver badges70 bronze badges

The algorithms with m-n can runs awfully long.

This one performs much better:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

answered Sep 22, 2013 at 13:13

netomnetom

3,3022 gold badges21 silver badges21 bronze badges

This version of code utilizes Euclid’s Algorithm for finding GCD.

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)

answered Feb 20, 2015 at 16:21

AnkushAnkush

4604 silver badges8 bronze badges

gcd = lambda m,n: m if not n else gcd(n,m%n)

answered Nov 2, 2015 at 8:48

Jonas ByströmJonas Byström

25k22 gold badges100 silver badges144 bronze badges

using recursion,

def gcd(a,b):
    return a if not b else gcd(b, a%b)

using while,

def gcd(a,b):
  while b:
    a,b = b, a%b
  return a

using lambda,

gcd = lambda a,b : a if not b else gcd(b, a%b)

>>> gcd(10,20)
>>> 10

answered Jan 31, 2019 at 8:16

def gcd(m,n):
    return gcd(abs(m-n), min(m, n)) if (m-n) else n

answered Jun 29, 2013 at 5:48

dansalmodansalmo

11.4k5 gold badges58 silver badges52 bronze badges

Very concise solution using recursion:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

answered May 16, 2018 at 12:02

a=int(raw_input('1st no n'))
b=int(raw_input('2nd no n'))

def gcd(m,n):
    z=abs(m-n)
    if (m-n)==0:
        return n
    else:
        return gcd(z,min(m,n))


print gcd(a,b)

A different approach based on euclid’s algorithm.

answered Jun 29, 2013 at 4:51

def gcdRecur(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    # Base case is when b = 0
    if b == 0:
        return a

    # Recursive case
    return gcdRecur(b, a % b)

Marko Gresak

7,9025 gold badges39 silver badges46 bronze badges

answered Nov 15, 2013 at 9:56

SHAMSSHAMS

191 bronze badge

I think another way is to use recursion. Here is my code:

def gcd(a, b):
    if a > b:
        c = a - b
        gcd(b, c)
    elif a < b:
        c = b - a
        gcd(a, c)
    else:
        return a

answered Oct 27, 2015 at 14:13

dexhunterdexhunter

5778 silver badges23 bronze badges

in python with recursion:

def gcd(a, b):
    if a%b == 0:
        return b
    return gcd(b, a%b)

answered Jul 27, 2014 at 20:54

def gcd(a,b):
    if b > a:
        return gcd(b,a)
    r = a%b
    if r == 0:
        return b
    return gcd(r,b)

lennon310

12.4k11 gold badges43 silver badges61 bronze badges

answered Dec 3, 2014 at 19:41

For `a>b`:

def gcd(a, b):

    if(a<b):
        a,b=b,a
        
    while(b!=0):
        r,b=b,a%r
        a=r
    return a

For either `a>b` or `a<b`:

def gcd(a, b):

    t = min(a, b)

    # Keep looping until t divides both a & b evenly
    while a % t != 0 or b % t != 0:
        t -= 1

    return t

answered Jan 25, 2015 at 17:55

I had to do something like this for a homework assignment using while loops. Not the most efficient way, but if you don’t want to use a function this works:

num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
    if num1 % x == 0:
        num1_list.append(x)
    x += 1
while y <= num2:
    if num2 % y == 0:
        num2_list.append(y)
    y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])

answered Apr 16, 2019 at 16:21

def _grateest_common_devisor_euclid(p, q):
    if q==0 :
        return p
    else:
        reminder = p%q
        return _grateest_common_devisor_euclid(q, reminder)

print(_grateest_common_devisor_euclid(8,3))

answered Jun 7, 2019 at 16:24

Sai prateekSai prateek

11.7k9 gold badges49 silver badges66 bronze badges

This code calculates the gcd of more than two numbers depending on the choice given by # the user, here user gives the number

numbers = [];
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?n")
for i in range(0, count):
  number = input("ENTER THE NUMBER : n")
  numbers.append(number)
numbers_sorted = sorted(numbers)
print  'NUMBERS SORTED IN INCREASING ORDERn',numbers_sorted
gcd = numbers_sorted[0]

for i in range(1, count):
  divisor = gcd
  dividend = numbers_sorted[i]
  remainder = dividend % divisor
  if remainder == 0 :
  gcd = divisor
  else :
    while not remainder == 0 :
      dividend_one = divisor
      divisor_one = remainder
      remainder = dividend_one % divisor_one
      gcd = divisor_one

print 'GCD OF ' ,count,'NUMBERS IS n', gcd

answered Jun 8, 2013 at 0:05

The value swapping didn’t work well for me. So I just set up a mirror-like situation for numbers that are entered in either a < b OR a > b:

def gcd(a, b):
    if a > b:
        r = a % b
        if r == 0:
            return b
        else:
            return gcd(b, r)
    if a < b:
        r = b % a
        if r == 0:
            return a
        else:
            return gcd(a, r)

print gcd(18, 2)

Delimitry

2,9474 gold badges29 silver badges39 bronze badges

answered Jun 18, 2013 at 20:03

troychroitroychroi

491 silver badge9 bronze badges

#This program will find the hcf of a given list of numbers.

A = [65, 20, 100, 85, 125]     #creates and initializes the list of numbers

def greatest_common_divisor(_A):
  iterator = 1
  factor = 1
  a_length = len(_A)
  smallest = 99999

#get the smallest number
for number in _A: #iterate through array
  if number < smallest: #if current not the smallest number
    smallest = number #set to highest

while iterator <= smallest: #iterate from 1 ... smallest number
for index in range(0, a_length): #loop through array
  if _A[index] % iterator != 0: #if the element is not equally divisible by 0
    break #stop and go to next element
  if index == (a_length - 1): #if we reach the last element of array
    factor = iterator #it means that all of them are divisibe by 0
iterator += 1 #let's increment to check if array divisible by next iterator
#print the factor
print factor

print "The highest common factor of: ",
for element in A:
  print element,
print " is: ",

greatest_common_devisor(A)

answered Mar 25, 2015 at 16:23

def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
    if (a%gcd==0 and b%gcd==0):
        return gcd
        break
    gcd-=1

answered May 25, 2018 at 12:47

Par basPar bas

2132 silver badges2 bronze badges

Here’s the solution implementing the concept of Iteration:

def gcdIter(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    if a > b:
        result = b
    result = a

    if result == 1:
        return 1

    while result > 0:
        if a % result == 0 and b % result == 0:
            return result
        result -= 1

answered Feb 15, 2019 at 21:40

Источник

В данном уроке мы узнаем, как найти наименьшее общее кратное (НОК) и наибольший общий делитель (НОД) с помощью языка программирования Python.

Но прежде чем мы начнем, давайте разберем, что обозначает Least Common Multiple (LCM) — наименьшее общее кратное.

НОК: наименьшее общее кратное

Это понятие арифметики и системы счисления. НОК двух целых чисел a и b обозначается НОК(a,b). Это наименьшее натуральное число, которое делится и на «а», и на «b».

Например: у нас есть два целых числа 4 и 6. Найдем НОК:

Кратные 4:

 
4, 8, 12, 16, 20, 24, 28, 32, 36,... and so on...

Кратные 6:

 
6, 12, 18, 24, 30, 36, 42,... and so on....

Общие кратные 4 и 6 — это просто числа, которые есть в обоих списках:

 
12, 24, 36, 48, 60, 72,.... and so on....

НОК — это наименьший общий множитель, поэтому он равен 12.

Поскольку мы поняли основную концепцию НОК, давайте рассмотрим следующую программу для нахождения НОК заданных целых чисел.

Пример:

 
# defining a function to calculate LCM 
def calculate_lcm(x, y): 
    # selecting the greater number 
    if x > y: 
        greater = x 
    else: 
        greater = y 
    while(True): 
        if((greater % x == 0) and(greater % y == 0)): 
            lcm = greater 
            break 
        greater += 1 
    return lcm   
 
# taking input from users 
num1 = int(input("Enter first number: ")) 
num2 = int(input("Enter second number: ")) 
# printing the result for the users 
print("The L.C.M. of", num1,"and", num2,"is", calculate_lcm(num1, num2))

Выход:

Enter first number: 3 
Enter second number: 4 
The L.C.M. of 3 and 4 is 12

Объяснение:

Эта программа сохраняет два числа в num1 и num2 соответственно. Эти числа передаются в функцию calculate_lcm(). Функция возвращает НОК двух чисел.

Внутри функции мы сначала определили большее из двух чисел, поскольку наименьшее общее кратное может быть больше или равно наибольшему числу. Затем мы используем бесконечный цикл while, чтобы перейти от этого числа и дальше.

На каждой итерации мы проверяли, идеально ли делят оба числа число. Если это так, мы сохранили число как НОК и вышли из цикла. В противном случае число увеличивается на 1, и цикл продолжается.

НОД: наибольший общий делитель

В этом разделе мы разберем, как найти Highest Common Factor (HCF) — наибольший общий делитель (НОД) в языке программирования Python.

Наибольший общий делитель двух или более целых чисел, когда хотя бы одно из них не равно нулю, является наибольшим положительным целым числом, которое без остатка делит целые числа. Например, НОД 8 и 12 равен 4.

Например:

У нас есть два целых числа 8 и 12. Найдем наибольший общий делитель.

Делители числа 8:

 
1, 2, 4, 8

Делители числа 12:

 
1, 2, 3, 4, 6, 12

НОД 8 и 12 равны 4.

Теперь давайте рассмотрим пример, основанный на нахождении НОД двух заданных чисел.

Пример:

 
# defining a function to calculate HCF 
def calculate_hcf(x, y): 
    # selecting the smaller number 
    if x > y: 
        smaller = y 
    else: 
        smaller = x 
    for i in range(1,smaller + 1): 
        if((x % i == 0) and(y % i == 0)): 
            hcf = i 
    return hcf 
 
# taking input from users 
num1 = int(input("Enter first number: ")) 
num2 = int(input("Enter second number: ")) 
# printing the result for the users 
print("The H.C.F. of", num1,"and", num2,"is", calculate_hcf(num1, num2))

Выход:

Enter first number: 8 
Enter second number: 12 
The H.C.F. of 8 and 12 is 4

Объяснение:

В приведенном выше фрагменте кода два целых числа, хранящиеся в переменных num1 и num2, передаются в функцию calculate_hcf(). Функция вычисляет НОД для этих двух чисел и возвращает его.

Внутри функции мы должны определить меньшее число, поскольку НОД может быть меньше или равен наименьшему числу. Затем мы использовали цикл for, чтобы перейти от 1 к этому числу.

На каждой итерации мы должны проверять, точно ли число делит оба входных числа. Если это так, мы должны сохранить число как НОД. По завершении цикла мы получаем наибольшее число, которое идеально делит оба числа.

1196-1017cookie-checkНахождение НОК и НОД в Python — примеры

Источник

Алгоритм Евклида – нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Решение задачи на языке программирования Python

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

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

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для определения НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Если условием завершения цикла является равенство хотя бы одной из переменных нулю (a == 0 or b == 0), то условием продолжения его работы является обратное этому условие – обе переменные должны иметь отличные от нуля значения (a != 0 and b != 0).

Блок-схема алгоритма Евклида

Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs(a) > abs(b):. Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

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

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

Пример:
Найти НОД для 30 и 18.
30 – 18 = 12
18 – 12 = 6
12 – 6 = 6
6 – 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция, вычисляющая НОД

def gcd(m, n):
    while m != n:
        if m > n:
            m = m - n
        else:
            n = n - m
    return n
 
 
a = int(input())
b = int(input())
 
print(gcd(a, b))

Функция `gcd` модуля `math`

В модуле math языка программирования Python есть функция gcd, вычисляющая наибольший общий делитель двух чисел.

>>> import math
>>> math.gcd(30, 18)
6

Больше задач в PDF

Источник

НОД с использованием функции gcd()

НОД с использованием рекурсии

Псевдокод алгоритма

Нахождение НОД с помощью цикла

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

Псевдокод алгоритма Евклида

Нахождение делителей числа

Простые делители числа

Сумма делителей

Количество делителей

Максимальный и минимальный делитель

For a>b:

For either a>b or a<b:

This code calculates the gcd of more than two numbers depending on the choice given by # the user, here user gives the number

НОК: наименьшее общее кратное

НОД: наибольший общий делитель

Алгоритм Евклида – нахождение наибольшего общего делителя

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

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

Функция, вычисляющая НОД

Функция gcd модуля math

Вам также может понравиться

Как найти площадь основания авс пирамиды

Как найти архив почты outlook

Как найти номер своего техосмотра

Добавить комментарий Отменить ответ

For `a>b`:

For either `a>b` or `a<b`:

Функция `gcd` модуля `math`