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

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

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

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

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

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

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

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

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


теги: математика php программирование философия числа алгоритм firefox браузеры opera

Здесь можно оставить коментарий, обязательны к заполнению только красные поля. Не пишите лишнего, и всё будет хорошо :)

Ваше имя:
Пароль (если желаете зарегистрировать имя):
Любимый URL (если указываете, то вставьте полностью):
Текст сообщения (до 1024 символов):
 
Введите 3-й код из этих чисел:
45765, 80263, 62711, 17848
 

18.11.2012, 22:07; рейтинг: 8987

  свежие записипоиск по блогукомментироватьстатистика

Наверх Яндекс.Метрика
© PerS
вход