Нередко возникает подзадача понять, является ли некоторое число простым или нет.
📌Число называется простым, если содержит всего 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.
Примеры кодов смотри на картинке👇🏻
Авторизуйтесь, чтобы оставить комментарий.