Эффективный поиск простых чисел на PHP

Если позволить себе пару строчек философии, то из четырёх арифметических операций суть человеческого подхода к бытию лучше всего выражает деление. Действительно, целые числа замкнуты относительно операций сложения, вычитания и умножения, не способных вывести результат за множество целых. С делением всё не так, именно оно - основной источник большинства вычислительных погрешностей, но оно же и приводит впервые к вещественным числам и почти бесконечному кругу связанных с ними задач. Наверное, отсюда и проистекает интерес к простым числам - они совершенны и просты как раз в своём нежелании делиться :) Какой-нибудь дюжине, конечно, далеко до тринадцати с точки зрения целостности...

Существует множество эффективных алгоритмов поиска простых чисел, основанных на решете Эратосфена или подобных "вычёркивающих" лишние числа стратегиях. Например, известно, что все простые числа, кроме 2, 3 и 5, лежат в одной из восьми следующих арифметических прогрессий: 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 и 30k+29.

Ясно, что платой за отсутствие проверки множества остатков от деления будет необходимость хранить вычеркнутые и невычеркнутые числа в каком-то массиве.

В частности, для реализации алгоритма, подобного решету, можно попробовать следующую процедуру:

• заполнить единичками или другим обозначением состояния "не вычеркнуто" массив a с номерами элементов от 2 до N включительно, где N - верхняя граница поиска;
• в цикле по i от 2 до корня квадратного из N проверить, не вычеркнут ли элемент a[i];
• если элемент не вычеркнут, во вложенном цикле по j от i2 до N включительно с шагом i вычеркнуть все элементы a[j] (на первом шаге вычеркнем числа, кратные двум, потом трём и т.д.).

Реализовать такое можно на чём угодно, но при настроенном локлахосте быстрее всего, пожалуй, написать скрипт на PHP. Проблема состоит в том, что все массивы в PHP фактически являются хешами, они очень медленные и жрут очень много оперативки. Зато PHP отлично умеет работать со строками и способен быстро обратиться к отдельным символам строки как к элементам массива - то, что нам и нужно! Тем более, строку эту можно заставить состоять из отдельных байт, а не более крупных единиц. Вот какая реализация на PHP показалась мне понятной и интересной:

<?php
//Лимит времени в сек.
set_time_limit (90);
//Верхняя граница поиска
define("N",10000000);
define("SQRT_N",floor(sqrt(N)));
//Поиск простых чисел     
$S = str_repeat("\1", N+1);
for ($i=2; $i<=SQRT_N; $i++) 
 if ($S[$i]==="\1") 
  for ($j=$i*$i; $j<=N; $j+=$i) $S[$j]="\0";
//Выводим в браузер, что получилось
for ($i=2; $i<N; $i++) if ($S[$i]==="\1") echo "<br>".$i;
?>

Скрипт "вываливает" числа прямо в браузер, очевидно, что это его самое слабое место...

При проверке скрипта существенно сказалась разница браузеров. Firefox стабильно сдыхал уже на верхней границе в 2500000 чисел, а вот "Опера" справилась с ней за 11 секунд при лимите времени в 60. На лимит в 5 млн чисел у Оперы ушло 24 секунды, и даже граница в 10 000 000 не вызывала особых сложностей - только лимит в 60 секунд пришлось повысить и ушло примерно 73-74 секунды. Да ещё и ход выполнения Opera хорошо отображала, так что ей +1.

Кстати, Internet Explorer и Google Chrome тоже справились с 10000000 чисел и зависли только при попытке выделить их через сочетание клавиш Ctrl+A, чтобы скопировать в буфер обмена :) Дальше экспериментировать не стал, некогда.

Вот они, простые числа, не превышающие значения 10 000 000, одним файлом.

 Скачать файл можно со страницы статьи

Всего их вышло 664 579, это примерно 6,65%, дальше, похоже, будет реже и примерно к границе поиска 10²² останется менее 2%.

Вообще-то, если применить немного программистской "эзотерики", можно сделать всё и одной строкой:

<?php
for($i=range(2,100);($a[]=array_shift($i))&&count($i)>0;)foreach($i as $k=>$v)if($v%end($a)==0)unset($i[$k]);
print_r ($a);
?>

(тег PHP и строка вывода результата не в счёт).

В этом коде находятся простые числа из диапазона [2,100], но вряд ли это будет работать быстрее предыдущего кода на больших интервалах, причина указана выше :)

Сервис для проверки числа на простоту и поиска целых делителей числа доступен в этой заметке.

Немного модифицировав скрипт, конечно, можно его заставить и выводить числа по мере работы.

18.11.2012, 22:07 [12785 просмотров]