Проверка числа на простоту

Как можно проверить число на простоту? Очевидно – если у числа нет делителей больше единицы и меньше самого числа, то оно простое. Значит, надо перебрать числа до $N$, и если оно поделится хотя бы на одно из них, то число окажется составным.

    bool if_prime(int N) {
        /* Перебираем с двух, т. к. на 0 нельзя делить, а на 1 поделится любое число,
        до N - 1, т. к. любое число делится само на себя.*/
        
        for (int i = 2; i < N; ++i) {
            if (N % i == 0)
                return false;
        }
        return true;
    }

Конечно, этот алгоритм сработает и будет возвращать правильные ответы. Но насколько быстро? Очевидно, что за $O(N)$ операций, но если $N$ окажется большим числом, например $10 ^ 9 + 7$? Как оптимизировать этот алгоритм?

Оптимизация в данном случае проста. Понятно, что если мы рассматриваем число $24$, нам не нужно проверять делимость на $23$, $22$, $21$, $20$ и так далее. Наибольший делитель числа $24$ – $12$, то есть $1 \over 2$. Надо ли все проверять до $\frac{1}{2}N$? Можно еще быстрее.

Выпишем все возможные разложения $24$ на два множителя, начиная с $2$:

$2 \times 12$

$3 \times 8$

$4 \times 6$

$6 \times 4$

$8 \times 3$

$12 \times 2$

Мы видим, что после какого-то момента произведения начинают повторяться. И даже отчасти понятно, когда. Для большего понимания рассмотрим еще один пример – $36$:

$2 \times 18$

$3 \times 12$

$4 \times 9$

$6 \times 6$

$9 \times 4$

$12 \times 3$

$18 \times 2$

Теперь стало ясно, что произведения повторяются после $\sqrt {N}$. Это и есть та самая граница, до которой нужно перебирать делители:

    bool if_prime(int N) {
        /*Корень из числа – это число в степени 1/2.
        Также лучше увеличить границы поиска на 1 элемент, т.к. int()
        округляет вниз.*/
        for (int i = 2; i <= int(sgrt(N)) + 1; ++i) {
            if (N % i == 0)
                return false;
        }
        return true;
    }