Как найти максимальный делитель числа python

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's user avatar


21.4k11 gold badges69 silver badges98 bronze badges

asked Jun 24, 2012 at 5:13

Luke D's user avatar


It’s in the standard library.

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

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

user545424's user avatar


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

netom's user avatar


3,3122 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
        return gcd_recursive(b, a % b)

answered Feb 20, 2015 at 16:21

Ankush's user avatar


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öm's user avatar

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

Mohideen bin Mohammed's user avatar


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

answered Jun 29, 2013 at 5:48

dansalmo's user avatar


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

preetika mondal's user avatar

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

def gcd(m,n):
    if (m-n)==0:
        return n
        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's user avatar

Marko Gresak

7,9025 gold badges39 silver badges46 bronze badges

answered Nov 15, 2013 at 9:56

SHAMS's user avatar


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)
        return a

answered Oct 27, 2015 at 14:13

dexhunter's user avatar


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

keajer's user avatar

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

lennon310's user avatar


12.4k11 gold badges43 silver badges61 bronze badges

answered Dec 3, 2014 at 19:41

dpeleg2000's user avatar

For a>b:

def gcd(a, b):

    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

Community's user avatar

answered Jan 25, 2015 at 17:55

Rao Baswaraj's user avatar


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:
    x += 1
while y <= num2:
    if num2 % y == 0:
    y += 1
xy = list(set(num1_list).intersection(num2_list))

answered Apr 16, 2019 at 16:21

Vanessa's user avatar

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


answered Jun 7, 2019 at 16:24

Sai prateek's user avatar

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 = [];
for i in range(0, count):
  number = input("ENTER THE NUMBER : n")
numbers_sorted = sorted(numbers)
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

Prashant's user avatar


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
            return gcd(b, r)
    if a < b:
        r = b % a
        if r == 0:
            return a
            return gcd(a, r)

print gcd(18, 2)

Delimitry's user avatar


2,9474 gold badges29 silver badges39 bronze badges

answered Jun 18, 2013 at 20:03

troychroi's user avatar


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: ",


answered Mar 25, 2015 at 16:23

user4713071's user avatar

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

answered May 25, 2018 at 12:47

Par bas's user avatar

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

Bikramjeet Singh's user avatar

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

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

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

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

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


gcd(a, b) 

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

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


# 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: Выйдите из программы.

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


# 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 
        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 с помощью циклов.


def GCD_Loop( a, b): 
    if a > b:  # define the if condition 
        temp = b 
        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.


# Create a program to find the GCD of two number in python using the Euclid's Algorithm. 
def find_hcf(a,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 вместе с вами, читаю, собираю и записываю информацию опытных программистов.

Полный текст программы
Полный текст программы

Простые делители числа 13195 – это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?

Начну разбор с функции is_simple(n), определяющей является ли число простым.

Задача Эйлера 3 - Наибольший простой делитель

Тут нужны несколько замечаний:

  • Простое число по определению делится лишь на 1 и само на себя.
  • При этом не обязательно для проверки делить на все числа от 1 до самого числа, т.к. если число вообще делится, то его можно представить в виде произведения двух чисел a*b, при это чем больше a, тем меньше b. После того как они сравняются (a==b), множители будут повторяться, т.е. a начнет принимать значения, которые ранее принимало b и наоборот.
  • Таким образом в функции число n для проверки делится на все числа до квадратного корня из проверяемого числа включительно.
  • Если встречается делитель, который нацело делит проверяемое число n, то работа функции прерывается оператором break и возвращается результат False
  • Если по окончании перебора всего ряда ни одно из чисел не делит проверяемое число n нацело, значит оно является простым и функция возвращает True
Задача Эйлера 3 - Наибольший простой делитель

Функция div_number(n) определяет максимальный делитель числа

  • Предполагается, что число n можно разложить на два множителя a*b
  • Число n последовательно делится на с каждой итерацией увеличивающееся (i+=1) число i
  • Как только число n делится без остатка искомый максимальный делитель найден
Задача Эйлера 3 - Наибольший простой делитель

Работа самой программы

  • Вычисляется максимальный делитель числа N с помощью функции div_number(N)
  • Полученный результат проверяется с помощью функции is_simple(N)
  • Если число простое, то работы программы заканчивается и выводится результат
  • Если нет, то число очередной раз делится и вычисляется максимальный делитель уже от него
Собственно ответ
Собственно ответ

Для тех, кто не понял задачу, подробнее можно почитать здесь. Так же тут есть формулы для более оптимального поиска кол-ва делителей используя простые числа.


Ваша функция KolDel работает не верно. Я переписала алгоритм, который работает верно, но он не оптимален. В качестве проверки можно использовать число 60 – имеет 12 делителей.

import math

def countDividers(n):
    if n <= 0: return 0 # условно будем так считать
    if n == 1: return 1

    k = 2 # делителей изначально 2, само число и единица.
    for i in range(2, round(math.sqrt(n)) + 1): 
        if n % i == 0:
            k += 1 if i == n // i else 2 #считаем и делитель и частное, если они не совпадают
    return k

def maxDividersCountAtRange(m , n):
    if m > n : m, n = n, m # меняем местами если m > n, только для учебных програм

    maxDivs = 0 #
    numberWithMaxDivs = [] #список чисел с максимальным числом делителей
    for i in range(m, n): #идем по интервалу
        d = countDividers(i) #записываем результат в переменную для оптимизации
        if d > maxDivs: #ищем максимум
            maxDivs = d
            numberWithMaxDivs = [] #очищаем список при изменении максимума
        if d == maxDivs:
            numberWithMaxDivs.append(i) #добавляем число в список

    return maxDivs, numberWithMaxDivs


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

Питон знаю мало, так что правки приветствуются


  • Начало
  • » Python для новичков
  • » Найти наибольший простой делитель

#1 Окт. 14, 2014 15:22:08

Найти наибольший простой делитель

Помогите решить задачу

Простыми делителями числа 13195 являются 5, 7, 13 и 29. Найти наибольший простой делитель заданного числа n.
Для этого объявить функцию f(n), которая вернет наибольший простой делитель n.


  • Пожаловаться

#3 Окт. 14, 2014 20:51:18

Найти наибольший простой делитель

а вообще наибольший простой делитель числа 13195 будет число math.fabs(13195)

Отредактировано sypper-pit (Окт. 14, 2014 20:57:04)


  • Пожаловаться

#4 Окт. 14, 2014 21:09:03

Найти наибольший простой делитель

def f(n):
    lst = [i for i in range(2, n // 2 +1) if not n % i]
    if not lst:
        return 1
    return max(lst)

(возврат 1 означает, что n – простое число). Но это самый неоптимальный вариант)

Отредактировано dimy44 (Окт. 14, 2014 21:11:21)


  • Пожаловаться

#5 Окт. 15, 2014 01:44:10

Найти наибольший простой делитель

а вообще наибольший простой делитель числа 13195 будет число math.fabs(13195)

13195 – составное число.

Если решать в лоб, то

Отредактировано py.user.next (Окт. 15, 2014 01:49:42)


  • Пожаловаться

#6 Окт. 15, 2014 07:14:35

Найти наибольший простой делитель

Тьфу. Конечно тот мой код неверен, невнимательно условие прочитал и искал просто наибольший делитель.


  • Пожаловаться

#7 Окт. 15, 2014 07:56:03

Найти наибольший простой делитель

#!/usr/bin/env python3
def factor(n):
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                n = int(n / i)
                yield i
def f(n):
    if n > 1:
        return max(factor(n))

>>> import max_pdelim
>>> max_pdelim.f(13195)

Отредактировано py.user.next (Окт. 15, 2014 08:13:45)


  • Пожаловаться

#8 Окт. 15, 2014 09:21:55

Найти наибольший простой делитель

объявить функцию f(n), которая вернет наибольший простой делитель n.

лучше одну, чем две 😀 😀

>>> def f(n):
...     pdelim = 2
...     while n > 1:
...         if n % pdelim == 0:
...             n = n/pdelim
...         else:
...             pdelim+=1
...     return pdelim
>>> f(13195)

Отредактировано Nata (Окт. 15, 2014 09:39:43)


  • Пожаловаться

#9 Окт. 15, 2014 11:20:28

Найти наибольший простой делитель


if n % i == 0: 
     n = int(n / i)

а зачем тут int()?

Отредактировано Nata (Окт. 15, 2014 11:21:31)


  • Пожаловаться

#10 Окт. 15, 2014 12:21:32

Найти наибольший простой делитель

а зачем тут int()?

Там она подаётся в range(), а результат деления – вещественный.

лучше одну, чем две

[guest@localhost max_pdelim]$ python3 -mdoctest max_pdelim.test 
File "max_pdelim.test", line 4, in max_pdelim.test
Failed example:
Expected nothing
File "max_pdelim.test", line 7, in max_pdelim.test
Failed example:
Expected nothing
1 items had failures:
2 of 14 in max_pdelim.test
***Test Failed*** 2 failures.
[guest@localhost max_pdelim]$

Для нуля там будет бесконечно большое простое число, а для единицы не будет таких чисел, так как она делится только на себя, не являясь простым.

Почему две функции? Потому что так можно найти не только максимальное.


  • Пожаловаться

  • Начало
  • » Python для новичков
  • » Найти наибольший простой делитель

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