Поиск простых чисел на 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 LinkedIn0Share on VKShare on Facebook0Share on Google+0Tweet about this on Twitter

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

Ваш e-mail не будет опубликован.

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