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

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

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

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

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

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

День!
решая задачу пришлось найти в сети алгоритм поиска всех делителей числа.
ну то есть для восьми надо выдать [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)))] 

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

This interesting question is much harder than it looks, and it has not been answered. The question can be factored into 2 very different questions.

1 given N, find the list L of N’s prime factors

2 given L, calculate number of unique combinations

All answers I see so far refer to #1 and fail to mention it is not tractable for enormous numbers. For moderately sized N, even 64-bit numbers, it is easy; for enormous N, the factoring problem can take «forever». Public key encryption depends on this.

Question #2 needs more discussion. If L contains only unique numbers, it is a simple calculation using the combination formula for choosing k objects from n items. Actually, you need to sum the results from applying the formula while varying k from 1 to sizeof(L). However, L will usually contain multiple occurrences of multiple primes. For example, L = {2,2,2,3,3,5} is the factorization of N = 360. Now this problem is quite difficult!

Restating #2, given collection C containing k items, such that item a has a’ duplicates, and item b has b’ duplicates, etc. how many unique combinations of 1 to k-1 items are there? For example, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} must each occur once and only once if L = {2,2,2,3,3,5}. Each such unique sub-collection is a unique divisor of N by multiplying the items in the sub-collection.

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

Представление числа в виде произведения простых множителей

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

[2, 3, 5, 7, 11, 13, 17, 19, 23, ldots]

Все остальные натуральные числа (кроме 1) называются составными, так как их
можно представить в виде произведения нескольких простых чисел. Например:

[12 = 2 * 2 * 3]

Часто это записывается со степенями простых множителей:

[12 = 2^2 * 3^1]

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

[x = p_1^{alpha_1} * p_2^{alpha_2} * ldots * p_n^{alpha_n} = prodlimits_i {p_i^{alpha_i}}]

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

Проверка числа на простоту

Чтобы проверить, является ли натуральное число (x) простым, достаточно просто
проверить, существует ли в отрезке ([2;sqrt{x}]) число, на которое делится (x).
Это достаточно очевидно: если бы существовало такое число (y), что (x) делится
на (y) и (sqrt{x} < y < x), то гарантированно существовало бы и число
(z = x/y), которое было бы меньше корня, а значит, изначального условия хватило
бы для проверки на простоту.

Реализация на C++:

1
2
3
4
5
6
7
8
9



bool is_prime(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}






Сложность этого алгоритма (O(sqrt{N})). Существуют алгоритмы, позволяющие

выполнять эту проверку быстрее (порядка (O(log^6 N))), но они исключительно

редко применяются в спортивном программировании.
Факторизация
Факторизацией называется разложение числа на простые множители. Алгоритм

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

приведённый выше. А именно: если у числа существует простой делитель, отличный

от него самого, то он не превышает корня из числа. Для факторизации числа нужно

перебрать все числа в промежутке ([2;sqrt{x}]), и попытаться разделить (x) на

каждое из них по очереди.
Реализация на C++ (Сложность: (O(sqrt{N}))):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



vector<int> factorize(int x) {
    vector<int> factors;

    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            factors.push_back(i);
            x /= i;
        }
    }

    if (x != 1) {
        factors.push_back(x);
    }

    return factors;
}






Корректность этого алгоритма доказать также несложно. Заметим, что если при

факторизации числа (x) мы нашли делитель (y), то нам, по факту, осталось

факторизовать число (x/y). Поэтому мы можем смело разделить число (x) на (y)

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

число (x/y) гарантированно не имеет делителей меньше (y), иначе мы бы их уже

нашли при факторизации (x).
Также очевидно, что все множители, найденные алгоритмом будут простыми.

Можно заметить, что каждый раз алгоритм находит минимальный из всех делителей

числа, и делит на него само число. Минимальный возможный делитель числа всегда

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

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

обрабатывается отдельной проверкой после цикла.
Также можно реализовать алгоритм в виде поиска пар ((p_i, alpha_i)), где

(p_i) — множитель, (alpha_i) — его степень:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



map<int, int> factorize(int x) {
    map<int, int> factors;

    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            factors[i]++;
            x /= i;
        }
    }

    if (x != 1) {
        factors[x]++;
    }

    return factors;
}






Поиск делителей
Поиск делителей числа и разложение его на множители — разные понятия,

хотя термины в какой-то степени схожи. Под делителями числа подразумевают

все числа, на которые оно делится. Пример для числа 20:



Множители
(2, 2, 5)


Делители
(1, 2, 4, 5, 10, 20)



Алгоритм поиска делителей числа (x) во многом похож на другие алгоритмы,

приведённые выше. Мы рассматриваем делители парами: для каждого делителя (y)

мы учитываем соответствующий ему (x/y). Один из этих делителей гарантированно

не превышает (sqrt{x}), поэтому, как и раньше, мы можем рассматривать только

промежуток ([1;sqrt{x}]).
Реализация на C++ (Сложность: (O(sqrt{N}))):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



vector<int> find_dividers(int x) {
    vector<int> dividers;

    for (int i = 1; i <= sqrt(x); i++) {
        if (x % i == 0) {
            dividers.push_back(i);

            //для корня из x не существует парного делителя
            if (i * i != x) {
                dividers.push_back(x / i);
            }
        }
    }

    return dividers;
}






Количество делителей
В качестве примера математических свойств представления числа в виде простых

множителей приведём связь между характеристиками простых множителей числа и

количеством его делителей.
Для этого давайте определим понятие делителя в контексте простых множителей.

Запишем числа (x) и (y) в следующем виде:
[x = p_1^{alpha_1} * p_2^{alpha_2} * ldots * p_n^{alpha_n}]
[y = p_1^{beta_1} * p_2^{beta_2} * ldots * p_n^{beta_n}]
Если какой-либо простой множитель не входит в разложение одного из чисел,

то его степень в следующих рассуждениях принимается за 0.
Утверждение: частное двух чисел можно записать следующим образом:
[{x over y} = p_1^{alpha_1 — beta_1} * p_2^{alpha_2 — beta_2} * ldots * p_n^{alpha_n — beta_n}]
Так как мы работаем с натуральными числами, это выражение имеет смысл тогда

и только тогда, когда все степени простых множителей целые и неотрицательные.

Отсюда можно выразить условие делимости двух чисел:
[forall i: alpha_i — beta_i ge 0]
или
[forall i: beta_i le alpha_i]
(Если вы не знакомы с подобной записью, (forall i) обозначает “для всех (i)”)
Из этого условия можно легко вывести количество делитей. Ещё раз запишем (x) в виде
[x = p_1^{alpha_1} * p_2^{alpha_2} * ldots * p_n^{alpha_n}]
Вспомним, что любому натуральному числу однозначно соответствует

разложение на простые множители, то есть, набор степеней. Другими словами,

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

(beta_i). С ней связано два условия:
(beta_i ge 0) 

(beta_i le alpha_i)
Значит, каждая из степеней (beta_i) может принимать (alpha_i + 1) различных

значений, и набор степеней (beta) однозначно описывает уникальный делитель.

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

образом:
[K = (alpha_1 + 1) * (alpha_2 + 1) * ldots * (alpha_n + 1) = prodlimits_i (alpha_i + 1)]
Реализация на C++:
1
2
3
4
5
6
7
8
9



int dividers_count(map<int, int>& factors) {
    int result = 1;

    for (map<int, int>::iterator it = factors.begin(); it != factors.end(); it++) {
        result *= it->second + 1;
    }

    return result;
}






Реализация на C++11:
1
2
3
4
5
6
7
8
9



int dividers_count(map<int, int>& factors) {
    int result = 1;

    for (auto p: factors) {
        result *= p.second + 1;
    }

    return result;
}






Это всего лишь одно из свойств простых множителей. Единственный способ

научиться решать задачи на эту тему — практика.