Перебор делителей и решето Эратосфена

Если ты напишешь решето Эратосфена, объяснишь, почему вычёркивать начинают с p², и оценишь, сколько простых среди чисел до миллиарда, - листай до «Теперь сам».

Как думаешь, сколько простых до миллиона

Простое число делится только на единицу и на себя: 2, 3, 5, 7, 11. Остальные числа больше единицы - составные: у них есть делитель поменьше. Чем дальше, тем простые реже: у большого числа больше возможных делителей.

Прежде чем читать дальше, попробуй угадать: какая доля чисел до миллиона - простые? Один процент? Одна десятая процента? И второй вопрос: сколько раз в среднем придётся вычеркнуть одно число, если для каждого простого вычёркивать все его кратные?

На что это похоже

Представь конвейер с коробками, пронумерованными подряд. Первый рабочий ставит отметку на каждую вторую коробку после второй. Второй - на каждую третью после третьей. Следующий рабочий встаёт у первой коробки без отметки - у пятой - и отмечает каждую пятую. Коробки, до которых не дотянулся никто, - простые числа.

Никто на конвейере не делит и не проверяет. Каждый рабочий просто шагает с постоянным шагом. Коробку не спрашивают «на что ты делишься» - к ней приходят те, на кого она делится.

Механизм: вычёркивание от p² и остановка на корне

числа до 30, вычёркиваем кратные:

 2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
17  18  19  20  21  22  23  24  25  26  27  28  29  30

p = 2:  4  6  8  10  12  14  16  18  20  22  24  26  28  30      начиная с 2² = 4
p = 3:  9  12  15  18  21  24  27  30                            начиная с 3² = 9
p = 5:  25  30                                                   начиная с 5² = 25
p = 7:  7² = 49 > 30 - стоп

остались: 2  3  5  7  11  13  17  19  23  29

Две детали делают решето быстрым.

Начинать с p². Кратные 2p, 3p, …, (p − 1) · p уже вычеркнуты: у каждого из них есть делитель меньше p, и к нему уже приходил рабочий с меньшим шагом. Первое кратное, до которого никто не добрался, - p · p.

Остановиться, когда p² > N. У составного числа до N есть делитель не больше √N - это то же наблюдение, что в переборе делителей. Значит, после простых до корня вычёркивать больше нечего.

Сколько это стоит. Простое p вычёркивает около N / p чисел. В сумме по всем простым до корня - N · (1/2 + 1/3 + 1/5 + 1/7 + …). Сумма обратных простых растёт, но чудовищно медленно: как логарифм от логарифма, ln ln N. Для миллиона это 2,6; для числа из ста цифр - 5,4. Настоящих вычёркиваний ещё меньше: старт с p² и остановка на корне убирают часть работы.

Запись ln - натуральный логарифм: логарифм по основанию e ≈ 2,718. От двоичного он отличается постоянным множителем, ln x ≈ 0,69 · log₂ x, а пишут именно его, потому что в законах о простых числах он стоит без поправочных коэффициентов.

Правило

Решето Эратосфена находит все простые до N за Θ(N · ln ln N) действий и N ячеек памяти: для каждого невычеркнутого p от 2 до √N вычёркиваются p², p² + p, p² + 2p, …. Перебор делителей проверяет одно число n за √n действий. Простых до N около N / ln N; среди чисел около N простым оказывается примерно одно из ln N.

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

Разбор: программа и замер против перебора

def resheto(N):
    prost = [True] * (N + 1)
    prost[0] = False
    prost[1] = False
    p = 2
    while p * p <= N:
        if prost[p]:
            k = p * p
            while k <= N:
                prost[k] = False
                k = k + p
        p = p + 1
    return prost

prost[i] отвечает на вопрос «простое ли i». Длина списка N + 1, чтобы индекс N существовал. Проверка if prost[p] пропускает составные p: их кратные уже вычеркнуты простыми делителями p.

Во втором столбце замера - resheto и цикл, считающий True в её ответе. В третьем - функция, которая проверяет одно число перебором делителей до корня, вызванная для каждого числа от 2 до N.

N            простых    решето с подсчётом    перебор делителей для каждого числа
1 000           168            7 525                    21 367
10 000        1 229           82 531                   406 267
100 000       9 592          889 913                 8 765 857
1 000 000    78 498        9 447 987                      -

N выросло вдесятеро - решето подорожало в 10,6-11 раз, почти линейно. Перебор дорожает в 19-22 раза: у него цена N · √N с поправкой на то, что составные отсеиваются рано.

Ответы на вопросы из начала. Простых до миллиона 78 498 - почти восемь процентов, гораздо больше, чем подсказывает интуиция. А вычёркиваний до миллиона - 2 122 048: в среднем 2,1 на число. Некоторые числа вычёркиваются по нескольку раз (30 - трижды), простые - ни разу.

Разбор: сколько простых и где решето кончается

N          простых до N     N / ln N     чисел на одно простое
10³             168            145               6,0
10⁴           1 229          1 086               8,1
10⁵           9 592          8 686              10,4
10⁶          78 498         72 382              12,7

Третий столбец - оценка из правила, она занижает на 8-14 процентов и с ростом N становится точнее. Последний столбец растёт на 2,1-2,3 с каждым нулём: это и есть ln 10 ≈ 2,3.

Отсюда практический счёт. Около миллиарда простое - одно из ln 10⁹ ≈ 20,7 чисел, а среди нечётных - одно из десяти. Замер: из тысячи нечётных чисел подряд после 10⁹ простыми оказались 99. Чтобы найти простое нужного размера, достаточно перебирать кандидатов подряд: от 10¹⁴ + 1 до первого простого, 10¹⁴ + 31, шестнадцать нечётных чисел.

Но проверять этих кандидатов решетом нельзя. Решету нужна память на все числа до N: для N = 10¹⁴ это двенадцать терабайт даже по биту на число. Решето - инструмент для вопроса «все простые до N» при N до миллиардов. Вопрос «простое ли вот это число из двадцати цифр» ему не по силам, а перебору делителей - тем более: последний урок первой главы показал, что √N - экспонента. Для одного большого числа нужна другая идея, и она в следующем уроке.

Что ломается без этого

Первое: вычёркивание от 2p. Ответ верный, работы больше: кратные 2p … (p − 1)p вычёркиваются повторно. При N = 10⁶ таких лишних вычёркиваний 75 791 - три с половиной процента.

Второе: [True] * N. Список на N элементов кончается индексом N − 1, и число N в него не попадает. Нужен N + 1.

Третье: единица. Единица не простая и не составная. Решето без prost[1] = False объявит её простой, и следующая же формула с разложением на множители сломается.

Четвёртое: память. Список из ста миллионов значений True в Python занимает 800 мегабайт: каждый элемент - ссылка в восемь байт. Для больших N берут bytearray - байт на число - или решето по отрезкам, которое держит в памяти только кусок диапазона и простые до корня.

Зачем это в работе

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

Разложение многих чисел сразу. Если в решете запоминать не «вычеркнуто», а «каким простым вычеркнуто впервые», получится таблица наименьших простых делителей. По ней любое число до N раскладывается на множители за число шагов, равное числу его множителей.

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

Теперь сам

1. Решето до 50. Какие простые будут вычёркивать и с какого числа начнёт каждое?
2. Оцени число простых до миллиарда по формуле N / ln N, если ln 10⁹ ≈ 20,7.
3. Почему число 30 вычёркивается трижды, а 49 - один раз?
4. Нужно проверить на простоту одно число 1 000 003. Решето или перебор делителей? Сколько делителей придётся перебрать?