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

Нередко возникает подзадача понять, является ли некоторое число простым или нет.

📌Число называется простым, если содержит всего 2 делителя: 1 и само число, не простое число называется составным.

Рассмотрим некоторые эффективные и не очень способы, как можно это сделать.

1. Наивный алгорим

Будем перебирать числа, начиная с 2, пока не не найдем делитель числа n. Если этот делитель будет равен n, то число будет простым, иначе у n есть нетривиальный делитель и число n будет составным.

📝Для числа n, берем число d(его делитель, минимальный = 2), и пока n не делится на d будем переходить к другому делителю.

Если число является простым, то первый такой делитель будет само число.

✖️Такой алгоритм нельзя назвать эффективным, так как в худшем случае мы пройдемся по всем делителям до n, его сложность = O(n)

2. Доходить до квадратного корня из числа

Такой алгоритм заканчивает работу либо при нахождении делителя, либо если проверяемый делитель станет больше корня из n. Чиcло n является простым, если алгоритм закончился по причине того, что проверяемый делитель стал больше, чем корень из n.

Его сложность = O(√n)

3. Перебор только нечетных делителей

Будем перебирать только нечетные делители, если число не делится на 2.

4. Метод 6 k ± 1

Все простые числа больше 3 имеют форму 6 k ± 1 , где k — любое целое число больше 0. Это потому, что все целые числа могут быть выражены как (6 k + i ) , где i = −1, 0, 1 , 2, 3 или 4.

💬Обрати внимание, что 2 делит (6 k + 0), (6 k + 2) и (6 k + 4), а 3 делит (6 k + 3) . Итак, более эффективный метод — проверить, делится ли n на 2 или 3, а затем проверить все числа в форме 6 k ± 1 <= √n.

Это в 3 раза быстрее, чем проверка всех чисел до √n.

Примеры кодов смотри на картинке👇🏻