Мотивация и контекст

Простые числа — атомы арифметики. Основная теорема арифметики утверждает, что каждое натуральное число единственным образом раскладывается в произведение простых. Это делает простые числа неизбежными участниками почти каждой задачи по теории чисел.

В соревновательном программировании простые числа встречаются повсюду: проверка числа на простоту, генерация простых до заданной границы, работа с большими простыми в криптографических задачах. Без быстрых алгоритмов даже проверка одного числа $n \sim 10^{18}$ на простоту с наивным подходом займёт $10^9$ операций — неприемлемо медленно.

Теория

Определение простого числа

Определение. Натуральное число $p > 1$ называется простым, если оно не имеет делителей, кроме 1 и самого себя. Число, не являющееся простым и большее 1, называется составным.

Число 1 не является ни простым, ни составным по определению — это важное соглашение, необходимое для единственности разложения в произведение простых.

Теорема (Основная теорема арифметики). Каждое натуральное число $n > 1$ представляется в виде произведения простых чисел, и это представление единственно с точностью до порядка множителей: $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \quad p_1 < p_2 < \cdots < p_k$

Доказательство (существование). Индукция по $n$. База: $n = 2$ — простое. Шаг: если $n$ простое, представление очевидно. Если $n$ составное, то $n = ab$, $1 < a, b < n$. По индукционному предположению, $a$ и $b$ раскладываются в произведения простых; перемножив, получаем разложение $n$.

Доказательство (единственность). Предположим, $n = p_1 \cdots p_s = q_1 \cdots q_t$ — два разложения. Из $p_1 \mid q_1 \cdots q_t$ и простоты $p_1$ следует $p_1 \mid q_j$ для некоторого $j$. Но $q_j$ — простое, значит $p_1 = q_j$. Сокращая $p_1 = q_j$ и применяя индукцию, получаем $s = t$ и разложения совпадают. $\square$

Теорема о бесконечности простых

Теорема (Евклид, ~300 до н.э.). Простых чисел бесконечно много.

Доказательство. Предположим противное: все простые — это конечный список $p_1, \ldots, p_k$. Рассмотрим $N = p_1 p_2 \cdots p_k + 1$. Это число больше 1 и должно делиться на какое-то простое $p_i$. Но тогда $p_i \mid N - p_1 \cdots p_k = 1$ — противоречие. $\square$

Пробное деление

Теорема. Если $n$ составное, то у него есть простой делитель $p \leq \sqrt{n}$

​.

Доказательство. Пусть $n = ab$, $1 < a \leq b < n$. Тогда $a \leq \sqrt{n}$

​ (иначе $ab > n$). У $a$ есть простой делитель $p \leq a \leq \sqrt{n}$. $\square$

Следствие: для проверки числа $n$ на простоту достаточно проверить делимость на все числа от 2 до $\lfloor\sqrt{n}\rfloor$

​⌋. Сложность: $O(\sqrt{n})$.

Оптимизация: проверяем 2 отдельно, затем только нечётные числа — ускорение в 2 раза. Ещё лучше — схема «2, 3 и числа вида $6k \pm 1$»: простое число $> 3$ не делится ни на 2, ни на 3, значит имеет вид $6k \pm 1$. Это даёт ускорение в 3 раза.

Решето Эратосфена

Алгоритм. Создаём массив флагов is_prime[0..n], изначально все true. Последовательно для каждого незачёркнутого $p$ начиная с 2 зачёркиваем все кратные $p^2, p^2+p, p^2+2p, \ldots$ Незачёркнутые числа — это простые.

Теорема. Решето Эратосфена выполняется за $O(n \log \log n)$ операций.

Доказательство. Для простого $p$ мы выполняем примерно $n/p$ операций зачёркивания. Суммируем по всем простым $p \leq n$: $\sum_{p \leq n, p \text{ простое}} \frac{n}{p} = n \sum_{p \leq n} \frac{1}{p}$

По теореме Мертенса, $\sum_{p \leq n} \frac{1}{p} = \ln \ln n + M + O(1/\log n)$, где $M \approx 0.2615$ — константа Мейсселя-Мертенса. Значит, сумма $\approx n \ln \ln n = O(n \log \log n)$. $\square$

Замечание. Решето за $O(n \log \log n)$ — практически линейное. Для $n = 10^7$ оно работает за ~0.05 секунды, для $n = 10^8$ — за ~0.5 секунды. Граница $n = 10^8$ обычно достижима с оптимизациями.

Сегментированное решето

Классическое решето требует $O(n)$ памяти, что неприемлемо для $n \sim 10^9$. Сегментированное решето решает эту проблему: оно находит простые на отрезке $[l, r]$, используя $O(\sqrt{r} + (r-l))$

​+(r−l)) памяти.

Алгоритм:

1. Находим все простые $p \leq \sqrt{r}$ классическим решетом.
2. Разбиваем $[l, r]$ на блоки размера $\sim \sqrt{r}$.
3. Для каждого блока и каждого малого простого $p$ зачёркиваем кратные $p$ в этом блоке.

Сложность: $O(\sqrt{r} + (r-l) \log \log r)$

​+(r−l)loglogr) — доминирует второй член.

Линейное решето (решето за O(n))

Классическое решето зачёркивает каждое составное число несколько раз. Линейное решето гарантирует, что каждое число зачёркивается ровно один раз — через своего наименьшего простого делителя (smallest prime factor, SPF).

Алгоритм:

• Поддерживаем список простых, найденных до сих пор.
• Для каждого $i$ от 2 до $n$: если $i$ не помечено, оно простое. Для каждого простого $p$ из нашего списка (пока $p \leq \text{spf}[i]$) помечаем $i \cdot p$ через $\text{spf}[i \cdot p] = p$.

Ключевой инвариант: $i \cdot p$ зачёркивается именно через наименьший простой делитель $p$ произведения $i \cdot p$ (так как $p \leq \text{spf}[i]$, это самый маленький делитель). Каждое составное число обрабатывается ровно один раз.

Тест Миллера–Рабина

Для чисел $n > 10^{12}$ пробное деление слишком медленно. Тест Миллера-Рабина — вероятностный тест на простоту, который с высокой вероятностью правильно определяет составные числа.

Малая теорема Ферма. Если $p$ — простое и $\gcd(a, p) = 1$, то $a^{p-1} \equiv 1 \pmod{p}$.

К сожалению, обратное неверно: числа Кармайкла (например, 561 = 3·11·17) удовлетворяют условию Ферма для всех оснований, но составные. Тест Миллера-Рабина устраняет этот изъян.

Теорема (Тест Миллера-Рабина). Пусть $n > 2$ нечётно, $n - 1 = 2^s \cdot d$ (где $d$ нечётно). Число $n$ — составное (свидетель — $a$), если:

1. $a^d \not\equiv 1 \pmod{n}$, И
2. $a^{2^r d} \not\equiv -1 \pmod{n}$ для всех $r = 0, 1, \ldots, s-1$.

Если ни одно из условий не выполнено, $n$ называется вероятно простым по основанию $a$ (или $a$ — сильный свидетель Ферма для $n$).

Доказательство корректности. Пусть $n$ простое. Тогда $a^{n-1} = a^{2^s d} \equiv 1 \pmod{n}$ по малой теореме Ферма. Рассматриваем цепочку квадратных корней: $a^d, a^{2d}, a^{4d}, \ldots, a^{2^s d} \equiv 1$. В этой цепочке последнее число равно 1. Значит, найдётся позиция, где при возведении в квадрат получается 1. Это возможно только если само значение было $\pm 1$ (так как уравнение $x^2 \equiv 1$ в поле $\mathbb{Z}_p$ имеет только решения $x = \pm 1$). Значит, либо $a^d \equiv 1$, либо для некоторого $r$: $a^{2^r d} \equiv -1$. Условие выполнено. Контрапозитивно: если условие нарушено, $n$ — составное.

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

Последний набор из 12 оснований покрывает все 64-битные числа (и даже больше — до $3.3 \times 10^{24}$), что на практике означает полностью детерминированный тест для всех задач в соревновательном программировании.

Доказательство корректности детерминированного варианта опирается на результаты вычислительных проверок (Bach, Sorenson, и др.) — было явно проверено, что для чисел в соответствующих диапазонах нет псевдопростых для данного набора оснований.

Распределение простых чисел

Теорема (Теорема о простых числах, Адамар и де ла Валле Пуссен, 1896). Обозначим $\pi(n)$ — количество простых, не превосходящих $n$. Тогда: $\pi(n) \sim \frac{n}{\ln n}$

Более точная аппроксимация — логарифмический интеграл $\text{Li}(n) = \int_2^n dt/\ln t$. Практическое правило: для $n = 10^6$ простых примерно $78\,498$, для $n = 10^9$ — около $50\,847\,534$.

Ключевые формулы

╔══════════════════════════════════════════════════════════════════╗
║  СВОДКА: ПРОСТЫЕ ЧИСЛА                                           ║
╠══════════════════════════════════════════════════════════════════╣
║  Пробное деление: O(√n)                                          ║
║  Решето Эратосфена: O(n log log n), память O(n)                  ║
║  Сегментированное решето: O(√R + (R−L) log log R), пам. O(√R)    ║
║  Линейное решето (SPF): O(n) времени и памяти                    ║
║  Тест Миллера-Рабина: O(k log²n), k = число оснований            ║
║  Детерминированный МР для n < 3.3×10²⁴: 12 оснований             ║
║  π(n) ≈ n / ln n (теорема о простых числах)                      ║
║  n − 1 = 2^s · d (d нечётно) — разложение для теста МР           ║
╚══════════════════════════════════════════════════════════════════╝

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

// ============================================================
// 1. Пробное деление — проверка числа на простоту за O(√n)
// ============================================================
bool is_prime_trial(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    // Проверяем числа вида 6k±1, начиная с 5
    // 5, 7, 11, 13, 17, 19, 23, 25(=5²), ...
    for (ll i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// ============================================================
// 2. Классическое решето Эратосфена за O(n log log n)
//    Использует bitset для экономии памяти (~n/8 байт)
// ============================================================
// Версия с vector<bool> — битовое кодирование автоматически
vector<bool> sieve_basic(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; (ll)i * i <= n; i++) {
        if (is_prime[i]) {
            // Начинаем с i*i, т.к. меньшие кратные уже зачёркнуты
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}

// Версия, возвращающая сами простые числа
vector<int> sieve_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; (ll)i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }

    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}

// ============================================================
// 3. Сегментированное решето для простых на [l, r]
//    Время: O(√r + (r-l) log log r), память: O(√r + (r-l))
// ============================================================
vector<ll> sieve_segment(ll l, ll r) {
    // Шаг 1: все простые до sqrt(r)
    int sq = (int)sqrt((double)r) + 1;
    vector<bool> small(sq + 1, true);
    small[0] = small[1] = false;
    for (int i = 2; i * i <= sq; i++)
        if (small[i])
            for (int j = i * i; j <= sq; j += i)
                small[j] = false;

    vector<int> small_primes;
    for (int i = 2; i <= sq; i++)
        if (small[i])
            small_primes.push_back(i);

    // Шаг 2: зачёркиваем в [l, r]
    // seg[i] отвечает за число l + i
    vector<bool> seg(r - l + 1, true);
    if (l == 1) seg[0] = false; // 1 не простое
    if (l == 0) { seg[0] = false; if (r >= 1) seg[1] = false; }

    for (int p : small_primes) {
        // Первое кратное p, которое >= l
        ll start = max((ll)p * p, ((l + p - 1) / p) * p);
        // Убеждаемся, что start != p (само p — простое)
        if (start == p) start += p;

        for (ll j = start; j <= r; j += p)
            seg[j - l] = false;
    }

    vector<ll> result;
    for (ll i = 0; i <= r - l; i++)
        if (seg[i])
            result.push_back(l + i);
    return result;
}

// ============================================================
// 4. Линейное решето (SPF — smallest prime factor)
//    Время: O(n), Память: O(n)
//    Бонус: для каждого числа хранит его наименьший простой делитель,
//    что позволяет факторизовать любое n <= N за O(log n).
// ============================================================
struct LinearSieve {
    int n;
    vector<int> spf;    // spf[i] = наименьший простой делитель i
    vector<int> primes; // список простых в порядке возрастания

    LinearSieve(int n) : n(n), spf(n + 1, 0) {
        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {       // i не помечено => i простое
                spf[i] = i;
                primes.push_back(i);
            }
            // Помечаем i * p для простых p <= spf[i]
            for (int p : primes) {
                if (p > spf[i] || (ll)i * p > n) break;
                spf[i * p] = p;
            }
        }
    }

    bool is_prime(int x) const {
        return x >= 2 && spf[x] == x;
    }

    // Факторизация за O(log n): делим последовательно на spf
    vector<pair<int,int>> factorize(int x) const {
        vector<pair<int,int>> result;
        while (x > 1) {
            int p = spf[x], cnt = 0;
            while (x % p == 0) { x /= p; cnt++; }
            result.push_back({p, cnt});
        }
        return result;
    }
};

// ============================================================
// 5. Тест Миллера–Рабина — детерминированный вариант
//    Работает корректно для всех n < 3.3 × 10^24
//    Время: O(k * log^2(n)), где k = 12 (число оснований)
// ============================================================

// Умножение по модулю без переполнения через __int128
ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

// Быстрое возведение в степень по модулю
ll powmod(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    if (base < 0) base += mod;
    while (exp > 0) {
        if (exp & 1) result = mulmod(result, base, mod);
        base = mulmod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

// Один раунд теста Миллера-Рабина для основания a
// Возвращает true, если n вероятно простое (или a не является свидетелем)
bool miller_rabin_round(ll n, ll a, ll d, int s) {
    ll x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true; // вероятно простое

    for (int r = 1; r < s; r++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true; // вероятно простое
    }
    return false; // СОСТАВНОЕ — a является свидетелем
}

bool is_prime_miller_rabin(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    // Представляем n-1 = 2^s * d
    ll d = n - 1;
    int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }

    // Детерминированный набор оснований для n < 3.3 * 10^24
    // Источник: https://miller-rabin.appspot.com/
    for (ll a : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL, 31LL, 37LL}) {
        if (a >= n) continue; // для маленьких n некоторые основания > n
        if (!miller_rabin_round(n, a, d, s))
            return false; // СОСТАВНОЕ
    }
    return true; // ПРОСТОЕ
}

// ============================================================
// Пример: использование всех реализаций
// ============================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Тест пробного деления
    cout << "is_prime(97) = " << is_prime_trial(97) << "\n";     // 1
    cout << "is_prime(100) = " << is_prime_trial(100) << "\n";   // 0

    // Решето до 30
    auto primes = sieve_primes(30);
    cout << "Простые до 30: ";
    for (int p : primes) cout << p << " ";
    cout << "\n"; // 2 3 5 7 11 13 17 19 23 29

    // Сегментированное решето: простые на [10^9, 10^9 + 100]
    ll L = 1000000000LL, R = L + 100;
    auto seg_primes = sieve_segment(L, R);
    cout << "Простые на [" << L << ", " << R << "]: ";
    for (ll p : seg_primes) cout << p << " ";
    cout << "\n";

    // Линейное решето
    LinearSieve ls(50);
    cout << "SPF[12] = " << ls.spf[12] << "\n"; // 2
    cout << "SPF[35] = " << ls.spf[35] << "\n"; // 5
    auto factors = ls.factorize(360);
    cout << "360 = ";
    for (auto [p, e] : factors) cout << p << "^" << e << " ";
    cout << "\n"; // 2^3 3^2 5^1

    // Тест Миллера-Рабина
    ll large_prime = 998244353; // простое
    ll large_composite = 999999937LL * 2; // составное
    cout << "998244353 простое: " << is_prime_miller_rabin(large_prime) << "\n"; // 1
    cout << "1999999874 простое: "
         << is_prime_miller_rabin(large_composite) << "\n"; // 0

    // Проверка числа Кармайкла: 561 = 3*11*17
    // Пробное деление правильно распознаёт его как составное
    cout << "561 (Кармайкл) простое по МР: "
         << is_prime_miller_rabin(561) << "\n"; // 0 — правильно!

    return 0;
}

Анализ сложности

Разбор задачи 1 — Подсчёт простых (простая задача)

Постановка. Дано $T$ запросов, каждый — число $n$ ($1 \leq n \leq 10^6$). Для каждого запроса выведите количество простых чисел, не превосходящих $n$.

Идея. Заранее построим префиксные суммы по массиву решета. Тогда каждый запрос отвечается за $O(1)$.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
int pi[MAXN]; // pi[i] = количество простых <= i

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<bool> is_prime(MAXN, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MAXN; i++) {
        if (is_prime[i])
            for (int j = 2*i; j < MAXN; j += i)
                is_prime[j] = false;
        // Префиксная сумма: pi[i] = pi[i-1] + (is_prime[i] ? 1 : 0)
        pi[i] = pi[i-1] + (is_prime[i] ? 1 : 0);
    }
    pi[1] = 0; pi[0] = 0;

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << pi[n] << "\n";
    }
    return 0;
}

Замечание. Решето запускаем один раз ($O(n \log \log n)$), каждый запрос — $O(1)$. Итого $O(n \log \log n + T)$.

Разбор задачи 2 — Простые на отрезке (средняя задача)

Постановка (CF 26A, аналог). Дано $T$ запросов, каждый — пара $(l, r)$ ($1 \leq l \leq r \leq 10^{12}$, $r - l \leq 10^6$). Для каждого запроса найдите все простые на $[l, r]$.

Идея. Ключевое наблюдение: $r - l \leq 10^6$, то есть сегмент небольшой, хотя $r$ большое. Применяем сегментированное решето.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Возвращает простые на [l, r] (оба включительно)
vector<ll> segment_sieve(ll l, ll r) {
    // Предварительно: простые до sqrt(r)
    int sq = (int)sqrt((double)r) + 2;
    vector<bool> small_sieve(sq + 1, true);
    small_sieve[0] = small_sieve[1] = false;
    for (int i = 2; i * i <= sq; i++)
        if (small_sieve[i])
            for (int j = i*i; j <= sq; j += i)
                small_sieve[j] = false;

    // Основное решето для отрезка [l, r]
    // Индекс j соответствует числу l + j
    int len = (int)(r - l + 1);
    vector<bool> seg(len, true);

    // Особый случай: 1 не простое
    if (l == 1) seg[0] = false;

    for (int p = 2; p <= sq; p++) {
        if (!small_sieve[p]) continue;
        // Первое кратное p, большее или равное l
        ll first = ((l + p - 1) / p) * p;
        if (first == p) first += p; // само p не зачёркиваем

        for (ll j = first; j <= r; j += p)
            seg[(int)(j - l)] = false;
    }

    vector<ll> result;
    for (int i = 0; i < len; i++)
        if (seg[i])
            result.push_back(l + i);
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll l, r;
        cin >> l >> r;
        auto primes = segment_sieve(l, r);
        for (ll p : primes)
            cout << p << "\n";
    }
    return 0;
}

Анализ. Для каждого запроса: $O(\sqrt{r})$

​) на построение малого решета (можно вынести за цикл) и $O((r-l) \log \log r)$ на сегмент. При $T$ запросах с общей суммой длин $\leq 10^7$ решение работает за доли секунды.

Важный нюанс. При вычислении first = ((l + p - 1) / p) * p возможно переполнение, если $l + p - 1 > 10^{18}$. Используйте вариант: first = (l / p) * p; if (first < l) first += p; — он безопаснее.

Разбор задачи 3 — Сложная задача уровня Div.1 D

Постановка (CF 1033G / аналог ICPC). Дано число $n$ ($2 \leq n \leq 10^{18}$). Найдите наибольший простой делитель $n$.

Обсуждение. Пробное деление за $O(n^{1/2})$ неприемлемо: для $n \sim 10^{18}$ это $10^9$ операций. Нужен быстрый тест простоты ($O(\log^2 n)$) и быстрая факторизация ($O(n^{1/4} \log n)$ — алгоритм Полларда, см. главу 3). Здесь сосредоточимся на части с тестом Миллера-Рабина.

Задача 3 (адаптированная). Дано $T$ чисел $n_i$ ($n_i \leq 10^{18}$). Для каждого числа определить, является ли оно простым.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

ll powmod(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mulmod(result, base, mod);
        base = mulmod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

bool miller_rabin_round(ll n, ll a) {
    if (n % a == 0) return n == a;
    ll d = n - 1;
    int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }

    ll x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int r = 1; r < s; r++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(ll n) {
    if (n < 2) return false;
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (!miller_rabin_round(n, a)) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        cout << (is_prime(n) ? "YES" : "NO") << "\n";
    }
    return 0;
}

Более сложная задача с тем же инструментом (CF 1033G). Даны $n$ чисел, нужно найти среди них те, у которых наибольший простой делитель максимален. Алгоритм:

1. Для каждого числа применить тест Миллера-Рабина (проверить, не простое ли оно само).
2. Если составное — применить $\rho$-алгоритм Полларда (глава 3) для полной факторизации.
3. Выбрать максимальный простой делитель.

Тест Миллера-Рабина здесь — ключевой строительный блок, без которого $\rho$-алгоритм не работает (он нужен для проверки, является ли найденный делитель простым).

Пример тестирования крайних случаев:

// Числа Кармайкла (псевдопростые по Ферма, но составные по МР):
// 561 = 3 * 11 * 17
// 41041 = 7 * 11 * 13 * 41
// 825265 = 5 * 7 * 17 * 19 * 73
assert(!is_prime(561));
assert(!is_prime(41041));

// Большие простые:
assert(is_prime(999999999999999877LL)); // простое
assert(is_prime(998244353LL));          // простое (известное из NTT)

// Квадрат большого простого:
assert(!is_prime(999999999999999877LL * 2)); // составное (переполнение?)
// Осторожно! 999999999999999877 * 2 переполняет long long!
// Нужно проверять: is_prime(n) и само n вписывается в ll.

Задачи для самостоятельного решения

Типичные ошибки

Ошибка 1: Переполнение в решете при вычислении i * i.

// НЕПРАВИЛЬНО для i ~ 50000, j ~ 2.5*10^9 > INT_MAX
for (int i = 2; i * i <= n; i++) { ... } // i*i может переполниться!

// ПРАВИЛЬНО: использовать long long для сравнения
for (int i = 2; (long long)i * i <= n; i++) { ... }
// или:
for (int i = 2; i <= (int)sqrt(n); i++) { ... } // но sqrt неточен!
// Самый надёжный вариант: (ll)i * i <= (ll)n

Ошибка 2: Начало зачёркивания не с i*i.

// НЕПРАВИЛЬНО: медленно — начинаем с 2*i, хотя 2*i, 3*i, ..., (i-1)*i
// уже зачёркнуты на предыдущих итерациях
for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;

// ПРАВИЛЬНО: начинаем с i*i
for (int j = i * i; j <= n; j += i) is_prime[j] = false;

Ошибка 3: Сегментированное решето — неправильное начало для p.

// Нужно НЕ зачёркивать само p (оно простое!)
ll first = ((l + p - 1) / p) * p;
if (first == p) first += p; // ← эта строка обязательна!

Ошибка 4: Тест Миллера-Рабина — забытый mulmod.

// НЕПРАВИЛЬНО: (base * base) переполняется для base ~ 10^9
x = x * x % n;

// ПРАВИЛЬНО:
x = (__int128)x * x % n;
// или через mulmod(x, x, n)

Ошибка 5: Неправильная обработка маленьких чисел в тесте МР.

// Если a >= n, тест для основания a не имеет смысла!
for (ll a : {2, 3, 5, 7, ...}) {
    if (a >= n) continue; // ОБЯЗАТЕЛЬНО пропускаем
    ...
}

Ошибка 6: Использование вероятностного МР в конкурсе без детерминированных оснований. Если использовать только малый набор оснований (например, только {2, 7, 61}), задача может быть специально составлена с числом, проходящим случайный тест. Всегда используйте детерминированный набор из 12 оснований.

Совет профессионала

Тест Миллера-Рабина с 12 основаниями детерминирован для $n < 3.3 \times 10^{24}$, что перекрывает все 64-битные числа. Однако у этого подхода есть малоизвестный враг — переполнение __int128. Числа $n \sim 10^{18}$, а $a^d \bmod n$ при вычислении использует числа до $n^2 \sim 10^{36}$, что вписывается в unsigned __int128 (максимум ~$3.4 \times 10^{38}$), но не в знаковый __int128 (максимум ~$1.7 \times 10^{38}$). Используйте unsigned __int128 или явный mulmod с __int128.

Ещё более продвинутый приём: на процессорах x86-64 с поддержкой инструкции mulx компилятор может автоматически оптимизировать (__int128)a * b % m до двух машинных инструкций вместо вызова функции. Для максимальной скорости тестируйте с флагами -O2 -march=native.

// Быстрый mulmod через встроенный __uint128_t (предпочтительно)
inline ll mulmod(ll a, ll b, ll m) {
    return (unsigned __int128)a * b % m;
}

Итог

Простые числа — фундаментальный объект математики и программирования. Мы изучили весь спектр алгоритмов — от $O(\sqrt{n})$

​) пробного деления до $O(k \log^2 n)$ теста Миллера-Рабина, способного проверить любое 64-битное число менее чем за микросекунду.

Ключевые выводы:

1. Пробное деление ($O(\sqrt{n})$) достаточно для $n \leq 10^{12}$.
2. Решето Эратосфена ($O(n \log \log n)$) — стандарт для генерации всех простых до $n \leq 10^8$.
3. Сегментированное решето позволяет работать с большими $r$, имея лишь $O(\sqrt{r})$ памяти.
4. Линейное решето за $O(n)$ даёт не только простые, но и SPF для мгновенной факторизации.
5. Тест Миллера-Рабина с 12 детерминированными основаниями покрывает весь диапазон $< 3.3 \times 10^{24}$ — используйте его для больших чисел.