Поиск простых чисел на PHP

Простые числа — это натуральные числа больше 1, которые делятся только сами на себя или на 1. Часто возникающая (например, при шифровании данных) задача — найти все простые числа от 2 до заданного N. Для этого придумано несколько алгоритмов разной эффективности. Давайте рассмотрим их реализацию на PHP.

Простой перебор делителей

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

Суть алгоритма: мы просто последовательно перебираем все числа от 2 до N и проверяем, простые они, или нет. Функция проверки на простоту перебирает все нечетные числа от 2 до квадратного корня из N и, если находит такое, на которое N делится без остатка, то число считается составным, а если не находит, то простым.

Эффективность такого алгоритма: O(n * sqrt(n))

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

Этот алгоритм как бы «просеивает» все числа от 0 до максимального N через условное решето несколько раз. Сначала последовательно исключаются все числа, кратные 2. Само число добавляется в массив простых чисел. Далее из оставшихся исключаются все числа, кратные следующему простому числу — трем. 4 уже было удалено из исходного массива, соответственно, следом удаляются все числа, кратные 5, и так далее, пока не будут перебраны все числа.

Вот пример решета Эратосфена на PHP:

Такой алгоритм имеет эффективность O(n * log(log n)) .

Метод нахождения псевдопростых чисел с использованием теста простоты Ферма

Данный метод позволяет находить простые числа гораздо быстрее предыдущих двух, однако, это будут псевдопростые числа, то есть числа, которые являются простыми лишь с некоторой (тем не менее, очень высокой, около 100%) вероятностью.

Здесь используется тест Ферма, который гласит: если p-простое число, то если возвести число n в степень (p-1), а потом взять результат возведения в степень по модулю p (остаток от деления на p), то в итоге получится 1.

Проблема в том, что если p не является простым, то есть вероятность, что в результате описанных вычислений вы все равно получите 1. Тогда n называется обманщиком Ферма, а если результат не равен 1, то число n называют свидетелем Ферма, так как оно верно указывает на составную природу тестируемого числа p. Вероятность того, что выбранное произвольно для теста число n окажется свидетелем Ферма 50%. Это, конечно, лишает смысла одиночный тест на простоту, но если провести несколько тестов с разными n, то вероятность можно многократно увеличить до приемлемых величин. Скажем, 10 последовательных тестов с разными n, которые выдали, что число является простым, дадут вероятность того, что число все же было составным, всего в 0.00098. 100 тестов и вовсе дадут число, кратное десяти в степени -31. Для практического применения такой низкой вероятности ошибки вполне достаточно.

Вот реализация поиска простых чисел с использованием теста Ферма на PHP:

Эффективность такого алгоритма O(n * log2n * log (log n) * log (log (log n)))

Кроме указанных алгоритмов существуют и такие, как:

Решето Сундарама

Решето Аткина

Кроме того, существует множество тестов простоты числа, как истинных, так и вероятностных. Возможно, в будущем я дополню эту статью реализацией других алгоритмов поиска простых чисел на PHP.

 

 

 

 

Поделиться: Share on LinkedIn
Linkedin
Share on VK
VK
Share on Facebook
Facebook
0Tweet about this on Twitter
Twitter

Оставить комментарий

Ваш адрес email не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Яндекс.Метрика