Вид числа по количеству делителей

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

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

Каждый делитель собирают из тех же простых множителей: двоек — от 0 до трёх штук, троек — от 0 до двух. Для 72 = 2³ · 3² это 4 · 3 = 12 вариантов. Разложим делители 72 сеткой: строка — сколько взяли двоек, столбец — сколько троек.

В общем виде: если n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ, то делителей (a₁ + 1)(a₂ + 1)…(aₖ + 1). Единица прибавляется, потому что множитель можно не брать вовсе. 360 = 2³ · 3² · 5, делителей 4 · 3 · 2 = 24. Формула считает и 1, и само число; без них делителей на 2 меньше.

Сетка заодно делит делители на чётные и нечётные. В верхней строке двоек нет — там три нечётных делителя: 1, 3, 9. В остальных строках двойка есть хотя бы одна, это девять чётных делителей.

Какие числа имеют ровно три делителя?

Только квадраты простых чисел, p²: 3 нельзя разложить в произведение чисел больше 1, значит, простой множитель один и стоит во второй степени. 4, 9, 25, 49, 121 — у 25 делители 1, 5, 25. Так же выводятся и другие случаи — выбери количество (p и q — разные простые):

2 делителя

p

3 делителя

p²

4 делителя

p³ или pq4 = 4 даёт p³, 4 = 2 · 2 даёт pq: 8 = 2³ и 15 = 3 · 5

5 делителей

p⁴

6 делителей

p⁵ или p²q

Где тут выигрыш? Числа до 10¹² ровно с пятью делителями — это p⁴, а p⁴ ≤ 10¹² значит p ≤ 1000. Вместо триллиона чисел — простые до тысячи, их 168:

found = [p ** 4 for p in range(2, 1001) if is_prime(p)]print(len(found), found[:5])

У каких чисел нечётное количество делителей?

Только у квадратов: делители идут парами, и лишь у квадрата одна пара — √n и √n — даёт один делитель. Сравни 36 и 40:

Поэтому «нечётное количество делителей» проверяют без делителей: isqrt(n) ** 2 == n — n полный квадрат.

Найди числа на отрезке [10⁹; 10⁹ + 2 000 000] ровно с тремя делителями и для каждого — наибольший делитель меньше самого числа. Два миллиона чисел, у каждого до 31 600 кандидатов в делители — это 6 · 10¹⁰ проверок. Как успеть?

Перебирать не числа, а простые p, у которых p² попадает на отрезок. Делители p² — 1, p и p², поэтому наибольший делитель меньше числа — это p.

low = 10**9high = 10**9 + 2_000_000for p in range(isqrt(low - 1) + 1, isqrt(high) + 1):    if is_prime(p):        print(p * p, p)

Кандидатов p около тридцати. Нижняя граница isqrt(low - 1) + 1 — наименьшее p, у которого p² ≥ low: если low не квадрат, isqrt(low) дал бы p² меньше low.

Числа до 10⁸ по маске 1*369 ровно с тремя делителями. Строить по маске или по виду числа?

По виду: чисел p² до 10⁸ мало — p не больше 10 000, — и у каждого проверяем только маску. По маске вышло бы 1111 кандидатов, и у каждого пришлось бы искать делители.

from fnmatch import fnmatch for p in range(2, 10**4 + 1):    if is_prime(p) and fnmatch(str(p * p), '1*369'):        print(p * p)

Перебор p не растёт, если маска станет сложнее: он зависит только от границы.

• Количество(a₁ + 1)(a₂ + 1)…(aₖ + 1) по разложению
• 3 делителяp²
• 4 делителяp³ или p · q
• 5 делителейp⁴
• Нечётное количествотолько полные квадраты
• Огромный отрезокперебирать p, а не числа