Nickolay.info. PHP. Эффективный поиск простых чисел на 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 от i² до 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, одним файлом.

Простые числа из диапазона 2-10000000 одним файлом, txt в архиве zip (1586 Кб)

Всего их вышло 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], но вряд ли это будет работать быстрее предыдущего кода на больших интервалах, причина указана выше :)

гостевая; E-mail