Как найти все делители натурального числа алгоритм

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

Как найти все делители числа

Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0.

Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1, -1, a, -a. Возьмем простое число 7: у него есть делители 7, -7, 1 и -1, и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1, -1, 367 и -367.

Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.

Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a=p1s1·p2s2·…·pnsn. Тогда натуральными делителями числа a будут следующие числа: d=p1t2·p2t2·…·pntn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

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

Для этого нужно выполнить следующие действия:

1. Выполнить каноническое разложение на простые множители и получить выражение вида a=p1s1·p2s2·…·pnsn.
2. Найти все значения d=p1t2·p2t2·…·pntn, где числа t1, t2, …, tn будут принимать независимо друг от друга каждое из значений t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

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

Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.

Продолжим усложнять наши примеры – возьмем четырехзначное число.

Как определить количество делителей конкретного числа

Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a=p1s1·p2s2·…·pnsn, нужно найти значение выражения (s1+1) ·(s2+1) ·…·(sn+1). О количестве наборов переменных t1, t2, …, tn мы можем судить по величине записанного выражения.

Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900, которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900=22·3·52·13. Значит, s1=2, s2=1, s3=2, s4=1. Теперь подставим значения s1, s2, s3 и s4 в выражение (s1+1) ·(s2+1) ·(s3+1) ·(s4+1) и вычислим его значение. Имеем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.

Как вычислить общие делители нескольких чисел

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

Разберем пару таких задач.

На этой странице вы узнаете

• Как быстро работает программа?
• Есть ли смысл перебирать делители после корня?
• Что количество делителей может сказать о самом числе?

Гадание на кофейной гуще или на картах Таро? Может, на ромашке? Хотя лучше не доверять свои отношения цветку. Наша судьба — только в наших руках. А судьба чисел предопределена заранее. Сегодня мы будем предсказывать их жизнь и судьбу по делителям. Но главная проблема — найти эти делители.

Постановка проблемы. Переборное решение

Встречали ли вы странных персонажей в задачах, которым резко понадобилось купить 50 арбузов? А что подумаете, если ваш учитель математики задаст найти число, у которого 50 делителей?

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

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

Идея в следующем:

1. Создадим список, в который мы сохраним все делители числа.
2. С помощью цикла for переберем все числа из диапазона от 1 до самого числа.
3. Если в переборе мы нашли такое число, которое является делителем исходного — остаток от деления будет равен 0 — сохраним это число в список.

В итоге мы получим список всех делителей исходного числа.

---

number = 1234567
dels = []

for i in range(1, number + 1):
	if number % i == 0:
		dels.append(i)

print(dels)
_____________________________________________________________________
Вывод: [1, 127, 9721, 1234567]

---

У этого метода есть очень большая проблема — время его работы.

Программа выполняет команды очень быстро, но не бесконечно быстро.

Замеры времени зависят от многих факторов, например, мощности компьютера. Но мы можем повысить эффективность работы программы. 

Ускоренный перебор делителей

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

Возьмем число 24. Найдя его делитель 2, мы сразу можем сказать, что у 24 есть еще один делитель — 12, потому что 12 = 24 / 2. Интересная мысль? Давайте ее развивать.

Найдем по такой логике все делители числа 16.

1. Самый простой делитель числа — 1. И по этой логике сразу найдем второй делитель — само число 16, так как 16 / 1 = 16.

1. Проверим число 2. Это делитель, так что сразу найдем его пару: 16 / 2 = 8.

1. Проверяем число 3 — это не делитель, его просто пропускаем.

1. При проверке числа 4 мы столкнемся с интересной ситуацией. Его парой будет 16 / 4 = 4 — то же самое число, а мы ищем различные пары. Значит, у корня числа пары не будет: найдя корень, мы найдем только один делитель.

Если мы продолжим перебор, числа 5, 6 и 7 — не будут делителями. А за ними — 8, делитель, который мы уже нашли.

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

Логика программы будет такой:

1. Перебираем числа от 1 до корня исходного числа.
2. Если мы нашли корень числа, добавляем в список делителей только его.
3. Если мы нашли не корень, а обычный делитель — добавляем в список сразу пару делителей.

Пример реализации ускоренного перебора делителей для числа 1234567000:

---

number = 1234567000
dels = []

for i in range(1, int(number ** 0.5) + 1):
	if i * i == number:
		dels.append(i)
	elif number % i == 0:
		dels.append(i)
		dels.append(number // i)

print(len(dels))
_____________________________________________________________________
Вывод: 64

---

Эта программа нашла все делители числа и выдала их количество — 64. А на ее работу ушло меньше секунды.

Но и это не панацея. Что, если нам придется проверить делители сразу нескольких чисел? Например, мы хотим найти все числа, у которых ровно 7 делителей, в диапазоне от 1 до 10000. 

Программу надо немного модифицировать:

1. заведем переменную-счетчик, которая будет считать подходящие числа;
2. number сделаем перебираемой переменной по нужному диапазону с помощью цикла for;
3. ускоренный перебор будет внутри перебора number;
4. в конце каждого шага цикла проверяем — если делителей у числа ровно 7, то увеличиваем наш счетчик на 1.

Теперь программа будет выглядеть следующим образом:

---

count = 0
for number in range(1, 10000):
	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)

	if len(dels) == 7:
		count += 1

print(count)
_____________________________________________________________________
Вывод: 2

---

Эта программа работала всего 0.2 секунды. Звучит неплохо, но давайте снова поднимать ставки:

1. диапазон 1 — 10000 — 0.2 секунды;
2. диапазон 1 — 100000 — 2.6 секунды;
3. диапазон 1 — 1000000 — 80.2 секунды.

Время снова увеличивается очень быстро. Что можно с этим сделать? 

Еще более ускоренный перебор делителей

Не считаем, что не нужно

Обратите внимание — программа выше нашла среди чисел 1–10000 всего 2 числа, имеющих ровно 7 делителей. А сколько же у остальных? Может быть и больше, может быть и меньше. Например, у числа 9864 делителей аж 24 штуки. Стоило ли тратить время на поиск их всех, если количество делителей больше 7?

Конечно, нет. Как только мы нашли 8 штук, мы уже можем понять, что анализировать число далее нам неинтересно. Значит, нужно остановить работу цикла.

Команда break полностью останавливает работу цикла.

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

---

count = 0
for number in range(1, 10000):
	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)
		if len(dels) > 7:
			break

	if len(dels) == 7:
		count += 1

print(count)

---

При этом завершится именно цикл перебора делителей i, так как break находится именно в нем, а цикл перебора number продолжит свою работу.

Давайте произведем замеры еще раз:

1. диапазон 1-10000 — 0.2 секунды;
2. диапазон 1-100000 — 2.1 секунды;
3. диапазон 1-1000000 — 53.5 секунды.

В последнем случае мы сэкономили около трети от времени работы программы. Но и это не предел.

Не считаем, что не нужно 2.0

Вернемся на несколько абзацев выше, когда мы искали делители числа 16. Мы нашли 5 делителей — 2 пары и 1 корень, который не даст пару. Это справедливо для любого числа: целый корень не будет давать пару ни с каким другим числом, а все остальные делители — будут. 

Нам нужны числа, у которых ровно 7 делителей. Следовательно, нам нужны числа, у которых есть целый корень. Это можно проверить, вычислив точный корень числа и его округленное значение. Если они совпадут, значит, округлять корень было некуда и он целый. 

Но как пропускать числа, которые нам не нужны?

Команда continue останавливает работу текущего шага цикла и сразу переходит к следующему.

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

Включить эту проверку в программу можно следующим образом:

---

count = 0
for number in range(1, 10000):
	if number ** 0.5 != int(number ** 0.5):
		continue

	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)
		if len(dels) > 7:
			break

	if len(dels) == 7:
		count += 1

print(count)

---

Снова посмотрим на время работы программы при разных диапазонах:

1. диапазон 1-100000 — 0.1 секунды;
2. диапазон 1-1000000 — 0.5 секунды;
3. диапазон 1-10000000 — 4.5 секунды;
4. диапазон 1-100000000 — 44.4 секунды.

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

Фактчек

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

Проверь себя

Задание 1.
Для чего нужен ускоренный перебор делителей?

1. Обычный перебор слишком скучный
2. Для большей точности вычислений
3. Для ускорения работы программы

Задание 2.
Найдите количество делителей числа 2568568668.

1. 5
2. 6
3. 7
4. 8

Задание 3.
Найдите, сколько чисел из диапазона от 2000 до 1002000 имеют ровно 5 делителей.

1. Ни одного
2. 1
3. 10
4. 8

Ответы: 1. — 3; 2. — 3; 3. — 4.

Здравствуйте, дорогие читатели! Как посчитать, сколько делителей у какого-нибудь числа? Если это число маленькое, то никаких сложностей не возникает. Например, для числа 10, мы легко можем найти все делители и посчитать их количество простым перебором. А вот как узнать, на какое количество различных чисел делится, например, число 720? Можно, конечно, опять же перебрать все делители, но это будет довольно трудоемко. При чем, 720 – еще и довольно маленькое число.

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

На самом деле, наша сегодняшняя формула будет даже проще, чем те, которые изображены на картинке выше)

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

Чудо-формула

Ну что ж, пора переходить от разговоров к делу.

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

Если не совсем понятно, о чем идет речь, то потом посмотрите пример ниже. На самом деле, все очень просто.

Так вот, после того, как мы найдем такое представление числа n, количество его делителей можно будет посчитать по формуле:

Посмотрим, как все это считается на примере

Пример

Раскладываем это число на простые множители, чтобы получить нужное представление:

Теперь, запишем число 720 в каноническом виде:

Ну и все, остается только применить чудо-формулу:

Вот и все, получили, что у числа 720 имеется 30 различных натуральных делителей. Стоит сделать замечание:

По этой формуле мы считаем количество делителей вместе с единицей и самим числом.

Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!

Читайте также ТОП-3 статьи, выпущенные в этом месяце на моем канале:

1. Quincy: робот, который обучит Ваших детей математике, английскому и рисованию
2. Почему вторая степень это квадрат, а третья – куб
3. Необычное тригонометрическое уравнение

День!
решая задачу пришлось найти в сети алгоритм поиска всех делителей числа.
ну то есть для восьми надо выдать [1,2,4,8], а не [2,2,2] – список делителей. Я переписал этот алгоритм наново, прошу “старших товарищей” подсказать как улучшить. Если есть время ))

def divisorss(n):
    from collections import Counter
    ls = get_ls(n)                  # for n=1568 -> ls = [2, 2, 2, 2, 2, 7, 7]
    pairs = dict(Counter(ls))       #  {2: 5, 7: 2}
    from itertools import product, starmap
    from operator import mul
    from functools import reduce
    #  список всех различных делитей числа
    bases = [b for b in pairs.keys()]   # [2, 7]
    #  список степеней, в которые возводятся уникальные делители для получения числа  
    powers = [[i for i in range(k+1)] for k in pairs.values()]
    # генерирование всех наборов для получения делителей исходного числа
    multi = product(*powers)
    #  сцепка списка оснований с возможными вариантами степеней
    wrk = (zip(bases,power) for power in multi)
    # наборы чисел, которые нужно перемножить для получения делителя
    rezzz = (starmap( pow, row) for row in wrk)
    # возвращение списка всех делителей
    return [reduce(mul,i) for i in rezzz]

например divisorss(1568) возвращает [1, 7, 49, 2, 14, 98, 4, 28, 196, 8, 56, 392, 16, 112, 784, 32, 224, 1568]

Функция get_ls(n) дает соответственно список разложения числа на произведение делителей

например такая:

def get_ls(n):
    """Разложить число на множители"""
    #result = [1]
    result = []
    i = 2
    while i*i <= n:
        if n % i == 0:
            n //= i
            result.append(i)
        else:
            i += 1
    if n > 1:
        result.append(n)
    return result

что можно улучшить?
Ну например, что лучше – reduce из functools или accumulate из itertools. Ну и вообще по алгоритму.

Понятно, что улучшения типа

return [reduce(mul,i) for i in (starmap(pow, row) for row in (zip(bases,power) for power in product(*powers)))] 

не интересны.

Была ли эта статья полезной?