Проверка на простоту за корень

Проверка на простоту за $O(\sqrt{N})$

$N$ - число, для которого мы определяем, простое ли оно.

Основные понятия

Рекомендуется сначала прочитать статью про простые числа.

Проверка на простоту за $O(N)$

Линейная проверка очень простая - надо просто перебрать все числа от $2$ до $N - 1$ и проверить, что $N$ не делится ни на одно из них. Отдельно обрабатывается случай для $N = 1$.

bool isPrime(int n) {
    if (n == 1) {
        return false;
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Ускорение до $O(\sqrt{N})$

Утверждение:
Пусть $N = a \times b$, причем $a \leq b$. Тогда $a \leq \sqrt N \leq b$.

Доказательство:
если $a \leq b < \sqrt{N}$, то $ab \leq b^2 < N$, но $ab = N$. А если $\sqrt{N} < a \leq b$, то $N < a^2 \leq ab$, но $ab = N$.

Иными словами, если число $N$ равно произведению двух других, то одно из них не больше корня из $N$, а другое не меньше корня из $N$.

Из этого следует, что если число $N$ не делится ни на одно из чисел $2, 3, 4, \ldots, \bigl\lfloor\sqrt{N}\bigr\rfloor$, то оно не делится и ни на одно из чисел $\bigl\lceil\sqrt{N}\bigr\rceil + 1, \ldots, N-2, N-1$, так как если есть делитель больше корня (не равный $N$), то есть делитель и меньше корня (не равный $1$). Поэтому в цикле for достаточно проверять числа не до $N$, а до корня.

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

---

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko