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

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

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

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

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

Встречали ли вы странных персонажей в задачах, которым резко понадобилось купить 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.

If your PC has tons of memory, a brute single line can be fast enough with numpy:

N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out: 
array([      1,       2,       4,       5,       8,      10,      16,
            20,      25,      32,      40,      50,      64,      80,
           100,     125,     128,     160,     200,     250,     320,
           400,     500,     625,     640,     800,    1000,    1250,
          1600,    2000,    2500,    3125,    3200,    4000,    5000,
          6250,    8000,   10000,   12500,   15625,   16000,   20000,
         25000,   31250,   40000,   50000,   62500,   78125,   80000,
        100000,  125000,  156250,  200000,  250000,  312500,  400000,
        500000,  625000, 1000000, 1250000, 2000000, 2500000, 5000000])

Takes less than 1s on my slow PC.

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

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

Что такое делители числа

В математике делителем натурального числа называют все числа, на которые это число делится без остатка. Например, делителями числа 12 являются числа 1, 2, 3, 4, 6 и 12, так как 12 делится на каждое из этих чисел без остатка. Количество делителей числа может быть разным в зависимости от самого числа. Например, у числа 12 имеется 6 делителей, а у числа 17 только 2 делителя (1 и само число).

Нахождение количества делителей числа с помощью цикла и проверки на остаток от деления

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

Вот пример кода на Python, который иллюстрирует этот подход:

num = int(input("Введите число: "))
count = 0

for i in range(1, num+1):
    if num % i == 0:
        count += 1

print("Количество делителей числа", num, "равно", count)

В этом примере мы сначала запрашиваем у пользователя число, затем проходим по всем целым числам от 1 до введенного числа (включительно) с помощью цикла for. Для каждого числа в этом диапазоне мы проверяем, является ли оно делителем введенного числа (то есть, делится ли число нацело на i). Если да, то увеличиваем счетчик делителей на 1. В конце выводим количество найденных делителей на экран.

Такой подход работает для любых чисел, включая большие числа. Однако, при больших числах он может работать медленно, поскольку требует перебора всех чисел от 1 до n. Далее мы рассмотрим более эффективные способы нахождения количества делителей числа.

Нахождение количества делителей числа с помощью математических свойств чисел

Используем свойство: Если число n имеет делитель d, то оно также имеет делитель n/d

Данный способ основан на математическом свойстве, что если число n имеет делитель d, то оно также имеет делитель n/d. Исходя из этого свойства, можно заметить, что достаточно искать делители только до квадратного корня числа n, так как все остальные делители можно получить путем деления n на найденный делитель до квадратного корня.

Таким образом, для нахождения всех делителей числа n, мы можем использовать цикл от 1 до int(sqrt(n))+1, и проверять, является ли i делителем n, если да, то добавлять i и n/i в список делителей.

Например, для числа n=100, квадратный корень из него равен 10. Поэтому, достаточно проверить делители от 1 до 11 (включая 10). Если делитель найден, то мы можем добавить его и соответствующий делитель, найденный путем деления n на найденный делитель, в список делителей. Таким образом, делители числа 100 будут: [1, 2, 4, 5, 10, 20, 25, 50, 100].

Вот пример кода на Python, который использует данный подход

import math

def count_divisors(num):
    # Инициализация счетчика делителей
    div_count = 0

    # Находим квадратный корень из числа
    sqrt_num = int(math.sqrt(num))

    # Проверяем числа от 1 до квадратного корня num
    for i in range(1, sqrt_num + 1):
        if num % i == 0:
            # Если i является делителем, увеличиваем счетчик на 1
            div_count += 1

            # Проверяем, является ли num/i также делителем (чтобы избежать дублирования)
            if i != num // i:
                div_count += 1

    # Возвращаем общее количество делителей
    return div_count

Эта функция принимает один аргумент num, который является целым числом. Она использует функцию sqrt() из модуля math, чтобы найти квадратный корень из числа, и затем проверяет все числа от 1 до этого корня на предмет деления на num. Если число делится без остатка, оно добавляется к счетчику делителей div_count. Затем функция проверяет, является ли num делителем num/i, чтобы избежать дублирования. Наконец, функция возвращает общее количество делителей.

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

Используем разложение на простые множители

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

Действительно, пусть дано число n = p_1^k_1 * p_2^k_2 * … * p_m^k_m, где p_1, p_2, …, p_m — простые числа, а k_1, k_2, …, k_m — их степени. Тогда каждый делитель числа n можно представить в виде d = p_1^i_1 * p_2^i_2 * … * p_m^i_m, где 0 <= i_j <= k_j для всех j от 1 до m. Таким образом, общее количество делителей числа n равно произведению (k_1 + 1) * (k_2 + 1) * … * (k_m + 1).

Для примера, давайте рассмотрим число 24. Его разложение на простые множители выглядит так: 24 = 2^3 * 3^1. Тогда количество делителей числа 24 равно (3 + 1) * (1 + 1) = 8. Это означает, что у числа 24 есть 8 делителей, а именно: 1, 2, 3, 4, 6, 8, 12 и 24.

Для вычисления количества делителей числа с помощью его разложения на простые множители в Python, нам необходимо воспользоваться функцией factorize() из библиотеки sympy. Она разлагает число на простые множители и возвращает список кортежей, каждый из которых содержит простой множитель и его степень. Затем мы можем вычислить количество делителей по формуле, описанной выше, и вернуть результат.

Вот пример кода, использующий функцию factorize() из библиотеки sympy для нахождения количества делителей числа:

from sympy import factorint

def count_divisors(n):
    factors = factorint(n)
    count = 1
    for factor in factors.values():
        count *= (factor + 1)
    return count

n = 24
print(f"Количество делителей числа {n}: {count_divisors(n)}")

Здесь мы сначала импортируем функцию factorint() из библиотеки sympy. Затем определяем функцию count_divisors(), которая принимает на вход число n и возвращает количество его делителей. Внутри функции мы используем функцию factorint() для разложения числа на простые множители и получаем словарь, где ключами являются простые множители, а значениями — их степени. Далее мы вычисляем количество делителей числа с помощью формулы, основанной на свойствах простых множителей, и возвращаем результат.

Затем мы просто вызываем функцию count_divisors() для числа 24 и выводим результат на экран. В данном случае результат будет равен 8, что соответствует количеству делителей числа 24 (1, 2, 3, 4, 6, 8, 12 и 24).