Простые числа и решето

Простое число — это число, у которого ровно два натуральных делителя: единица и оно само. Двойка простая, единица — нет: у неё всего один делитель.

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

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

Для $n = 10^{12}$ это миллион шагов — доли секунды. Отличный инструмент.

Пока не спросят миллион раз

А теперь задача: сколько простых чисел не превосходит миллиона?

Тем же способом это миллион проверок, каждая до тысячи шагов, — порядка $10^9$ действий. Минуты работы.

Вот это и есть развилка всего занятия. Один вопрос про большое число — проверка за корень. Много вопросов про числа поменьше — решето. Выбор определяется не тем, какой способ «лучше», а тем, сколько раз спрашивают.

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

Заводим список отметок «простое» на все числа до $n$. Идём по числам: если число ещё не вычеркнуто, оно простое — и мы вычёркиваем все его кратные.

flags = bytearray([1]) * (n + 1)
flags[0] = flags[1] = 0

i = 2
while i * i <= n:
    if flags[i]:
        for m in range(i * i, n + 1, i):
            flags[m] = 0
    i += 1

Две детали, которые легко пропустить

Почему вычёркивание начинается с $i^2$, а не с $2i$? Потому что все меньшие кратные уже вычеркнуты. Число $i \cdot k$ при $k < i$ имеет множитель $k$, меньший $i$, — а по нему мы уже проходили раньше. Начинать с $i^2$ не оптимизация ради оптимизации: это ровно та граница, ниже которой работать бессмысленно.

Почему внешний цикл идёт только до корня? По той же причине. Если $i > \sqrt{n}$, то первое вычёркиваемое число $i^2$ уже больше $n$, и вычёркивать нечего.

Сколько это стоит

Вычёркиваний получается примерно $n \ln \ln n$ — это почти линейно. Для $n = 10^7$ решето строится за доли секунды.

Платим памятью: список на $n + 1$ ячейку. Для $10^7$ в виде bytearray это десять мегабайт — нормально. Для $10^9$ уже гигабайт, и так делать нельзя.

Почему в решете вычёркивание кратных числа $i$ начинают с $i^2$, а не с $2i$?

Любое натуральное число больше единицы раскладывается на простые множители, причём единственным способом. Найти это разложение можно тем же перебором до корня:

result = []
i = 2
while i * i <= n:
    while n % i == 0:
        result.append(i)
        n //= i
    i += 1
if n > 1:            # остаток — тоже простой множитель
    result.append(n)

Три вещи, которые тут происходят

Проверять простоту i не нужно. Когда цикл доходит до составного i, все его простые множители уже вычеркнуты делением, поэтому n % i == 0 для составного i просто не выполнится. Так что делить можно подряд, на 2, 3, 4, 5, — лишние проверки ничего не изменят.

Условие цикла смотрит на текущее n, а оно уменьшается. Это делает перебор быстрее: после деления на маленькие простые корень становится меньше.

Последняя строчка обязательна. После цикла n — это либо единица, либо простое число. Простое, потому что если бы остаток был составным, у него нашёлся бы делитель не больше его корня, а все такие делители мы уже перебрали. Забыть эту строчку — самая частая ошибка темы: для $n = 14$ вывод получится 2 вместо 2 7.

Когда чисел много

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

spf = list(range(limit + 1))
i = 2
while i * i <= limit:
    if spf[i] == i:                     # i простое
        for m in range(i * i, limit + 1, i):
            if spf[m] == m:             # ещё не отмечено
                spf[m] = i
    i += 1

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

Сколько простых чисел не превосходит 30? Введите целое число.

Задача: сколько простых чисел лежит между $10^{12} - 10^6$ и $10^{12}$?

Обычное решето до $10^{12}$ построить нельзя — это терабайт памяти. Проверять каждое число по отдельности — миллион проверок по миллиону шагов, слишком долго. Но выход есть, и он опирается на ту же мысль про корень.

Составное число, не превосходящее $R$, обязательно имеет простой делитель не больше $\sqrt{R}$. Для $R = 10^{12}$ это миллион.

Значит достаточно двух шагов:

1. Построить обычное решето до $\sqrt{R}$ — это миллион ячеек, недорого.
2. Завести отметки только на нужный отрезок — $R - L + 1$ ячеек — и вычеркнуть в нём кратные каждого найденного простого.

flags = bytearray([1]) * (high - low + 1)
for p in base_primes:
    start = max(p * p, (low + p - 1) // p * p)   # первое кратное p не меньше low
    for m in range(start, high + 1, p):
        flags[m - low] = 0                       # сдвиг индексов!

Это называется сегментным решетом. Память — по длине отрезка, а не по величине чисел.

Два места, где ошибаются: сдвиг индексов (в списке ячейка с номером m - low, а не m) и случай $L = 1$ — единицу надо вычеркнуть вручную, её ни одно простое не вычеркнет.

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

Единица и ноль. Не простые и не составные. В решете их надо вычеркнуть отдельной строкой — сам алгоритм этого не сделает.

Список на единицу короче. bytearray(n) даёт ячейки с номерами от 0 до $n - 1$, а нам нужно и само $n$. Признак: неверный ответ ровно тогда, когда $n$ простое.

Решето вместо проверки и наоборот. Решето до $10^{12}$ не построить, а проверять миллион чисел по отдельности слишком долго. Прежде чем писать, прикиньте: сколько раз спросят и насколько большие числа.

Забытый сдвиг в сегментном решете. Обращение flags[m] вместо flags[m - low] либо упадёт, либо молча испортит ответ.

Как проверять себя

• $n = 1$ и $n = 2$ — крайние случаи всех задач темы;
• $n$ простое и $n$ — степень двойки;
• произведение двух больших простых: 999 962 000 357 = 999 983 · 999 979 — здесь перебору до корня придётся дойти почти до конца;
• в задачах на отрезок — $L = 1$ и отрезок из одного числа.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Перед каждой задачей отвечайте себе на один вопрос: спрашивают про одно число или про все сразу? От ответа зависит, что писать — проверку за корень или решето.

В задачах со звёздочкой числа доходят до триллиона, а отрезок короткий. Это прямая подсказка на сегментное решето.

Задача: «дано $n$ от 1 до $10^{12}$; выведите его простые множители по возрастанию, с повторами».

Ученик написал:

n = int(input())

factors = []
i = 2
while i * i <= n:
    while n % i == 0:
        factors.append(i)
        n //= i
    i += 1

print(*factors)

На числах 12, 36 и 1024 ответ верный, по времени решение проходит.

Найдите вход, на котором оно ошибается, объясните причину и предложите исправление.