Решето Эратосфена и факторизация

Как быстро найти все простые числа до миллиона и разложить число на простые множители. Фундамент задач теории чисел.

Решето Эратосфена — алгоритм, находящий все простые числа до N за O(N log log N), последовательно вычёркивая кратные каждого найденного простого.

Зачем это нужно

Простые числа и разложение на множители — основа целого пласта олимпиадных задач: делимость, количество и сумма делителей, функция Эйлера, взаимная простота, диофантовы уравнения. Когда нужно много раз проверять простоту чисел до некоторого предела или находить простые множители, наивные методы (проверять делимость на всё подряд) слишком медленны. Решето и факторизация за корень дают эффективные инструменты, которые встречаются буквально в каждом олимпиадном наборе по математике.

Идея решета «на пальцах»

Чтобы найти все простые до N, поступим от противного: будем вычёркивать составные. Берём первое непомеченное число (2 — простое) и вычёркиваем все его кратные (4, 6, 8, ...). Следующее непомеченное (3) — простое, вычёркиваем его кратные. И так далее. Что осталось непомеченным — простые. Это как просеивание песка через сито: составные «проваливаются». Хитрость: начинать вычёркивание можно с i·i (меньшие кратные уже вычеркнуты меньшими простыми), а внешний цикл вести только до √N.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False        # 0 и 1 — не простые
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # вычёркиваем кратные i, начиная с i*i
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

print("Простые до 30:", sieve(30))
print("Простых до 50:", len(sieve(50)))

Два важных оптимизационных момента. Внешний цикл идёт лишь до √n: если у числа есть делитель больше корня, то есть и парный делитель меньше корня, который его уже вычеркнул. Внутренний цикл стартует с i·i, а не с 2i: кратные i, меньшие i² (например 2i, 3i), уже вычеркнуты простыми 2, 3 и т. д. Итоговая сложность — O(N log log N), что практически линейно.

Вывод:

Простые до 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Простых до 50: 15

Факторизация: разложение на простые

Чтобы разложить одно число x на простые множители, не нужно решето — достаточно перебирать делители d от 2 до √x. Делим x на каждый d, пока делится, считая степень. Ключевое наблюдение: после того как мы выделили все делители до √x, если осталось число > 1 — это простой множитель (он больше корня и может быть только один).

def factorize(x):
    factors = {}
    d = 2
    while d * d <= x:                  # перебираем делители до корня
        while x % d == 0:
            factors[d] = factors.get(d, 0) + 1   # степень множителя
            x //= d
        d += 1
    if x > 1:                          # остался крупный простой множитель
        factors[x] = factors.get(x, 0) + 1
    return factors

print("Разложение 360:", factorize(360))
print("Разложение 97 :", factorize(97))
print("Разложение 100:", factorize(100))

Разберём 360 = 2³ · 3² · 5: делим на 2 трижды (остаётся 45), на 3 дважды (остаётся 5), и 5 — последний множитель. Для простого числа 97 цикл до корня ничего не находит, и оно само остаётся как множитель степени 1. Сложность — O(√x), чего достаточно для чисел до ~10^12–10^18.

Вывод:

Разложение 360: {2: 3, 3: 2, 5: 1}
Разложение 97 : {97: 1}
Разложение 100: {2: 2, 5: 2}

Применения разложения

Из разложения x = p₁^a₁ · p₂^a₂ · ... мгновенно получаются полезные величины:

Величина	Формула
Число делителей	`(a₁+1)·(a₂+1)·...`
Сумма делителей	произведение `(p^(a+1)−1)/(p−1)`
Функция Эйлера φ(x)	`x · ∏(1 − 1/p)`

Например, у 360 = 2³·3²·5 число делителей = (3+1)(2+1)(1+1) = 24. Это типичные подзадачи олимпиадной теории чисел.

Подводные камни

Решето или факторизация? Решето хорошо, когда нужно много простых до предела; для разложения одного большого числа достаточно перебора до корня без решета.
Память решета. Массив на N+1 булевых; при N = 10^8 это уже сотни МБ — следи за лимитом.
Начинай вычёркивание с i·i и веди внешний цикл до √N — без этого решето заметно медленнее.
Не забудь финальную проверку if x > 1 в факторизации — иначе потеряешь последний большой простой множитель.

Итог

Решето Эратосфена находит все простые до N за O(N log log N), вычёркивая кратные с i·i.
Факторизация одного числа — перебор делителей до √x; остаток > 1 — последний простой множитель.
Из разложения легко получить число и сумму делителей, функцию Эйлера.
Решето — для множества простых до предела; перебор до корня — для разложения отдельного числа.