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

Проверка одного числа

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long d = 2; d * d <= n; d++)
        if (n % d == 0) return false;
    return true;
}

Проверять до корня достаточно: если $n = p \cdot q$, то один из множителей не превосходит $\sqrt{n}$. Значит, не найдя делителя до корня, мы не найдём его вовсе.

Это даёт $O(\sqrt{n})$ — для одного числа до $10^{18}$ это миллиард операций, многовато. Но для чисел до $10^{12}$ (миллион шагов) вполне подходит.

Условие пишут именно как d * d <= n, а не d <= sqrt(n): корень считается в вещественных числах и на границе иногда ошибается в последнем разряде.

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

Когда нужны все простые до $n$, проверять каждое по отдельности расточительно. Решето находит их все сразу.

vector<bool> isComposite(n + 1, false);
for (int p = 2; (long long)p * p <= n; p++)
    if (!isComposite[p])
        for (int m = p * p; m <= n; m += p)
            isComposite[m] = true;

Идея: берём очередное непомеченное число — оно простое, — и вычёркиваем все его кратные.

Две детали, которые экономят время. Внутренний цикл начинается с $p^2$, а не с $2p$: меньшие кратные уже вычеркнуты меньшими простыми. Внешний идёт до корня: у составного числа обязательно есть множитель не больше корня, значит оно уже вычеркнуто.

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

Для каждого простого $p$ вычёркивается $n/p$ чисел. Сумма $\sum_{p \le n} n/p$ равна примерно $n \ln \ln n$ — это почти линия: при $n = 10^7$ множитель $\ln \ln n$ меньше трёх.

Память — $n$ бит при использовании vector<bool>, то есть около мегабайта на $10^7$. Это и есть ограничение: решето до $10^9$ в память уже не помещается.

Минимальный простой делитель

Гораздо полезнее обычного решета его версия, которая для каждого числа запоминает наименьший простой делитель.

vector<int> minPrime(n + 1, 0);
for (int p = 2; p <= n; p++)
    if (minPrime[p] == 0)
        for (long long m = p; m <= n; m += p)
            if (minPrime[m] == 0) minPrime[m] = p;

После этого разложение любого числа до $n$ занимает $O(\log n)$ вместо $O(\sqrt{n})$:

while (x > 1) {
    int p = minPrime[x];
    while (x % p == 0) x /= p;
    // p — очередной простой делитель
}

Шагов не больше логарифма, потому что каждое деление уменьшает число как минимум вдвое.

Это стандартный ход, когда в задаче надо разложить много чисел: одно решето, а дальше каждое разложение почти бесплатно.

Сегментное решето

Если нужны простые в промежутке $[L, R]$, где $R$ до $10^{12}$, а длина промежутка невелика, полное решето не построить. Но можно построить решето до $\sqrt{R}$ и вычеркнуть их кратные внутри промежутка.

Память тогда — длина промежутка, а не $R$. Приём тот же самый, просто смещённый.

Сколько вообще простых

Простых до $n$ примерно $n / \ln n$. До миллиона их 78 498, до миллиарда — около 50 миллионов.

Практический вывод: простые не редкость. Среди случайных девятизначных чисел примерно каждое двадцатое простое, и в задачах «найдите простое рядом с $x$» перебор соседей работает быстро.