Как найти простые числа в php

Поиск простых чисел разными способами. Сравнение алгоритмов поиска простых чисел по памяти и времени.

Подготовка

Записать php 7 в папку c:php, поместить в эту же папку файл php7.bat со следующим содержимым. Создать папку c:phplocalhost, в неё положить php файлы.

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

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

Числа проверяются на делимость на простые числа, не превышающие квадратный корень из этого числа. По мере нахождения простых чисел они записываются в массив, который используется для проверки следующих чисел на делимость.

<?
ini_set('max_execution_time',0);

$time=time();

$max=10_000_000;
$primes=array();
$primes[]=2;
$primes[]=3;
$primes[]=5;

for($i=7;$i<$max;$i++)
{
  $sqrt_i=(int)sqrt($i);

  for($j=0;$primes[$j]<=$sqrt_i;$j++)
    if($i%$primes[$j]==0) continue 2;

  $primes[]=$i;
}

echo 'time: ';
echo time()-$time.'<br>';
echo 'memory: '.number_format(memory_get_peak_usage(true)).'<br>';
echo 'primes/all: '.number_format(sizeof($primes));
echo ' / '.number_format($max);

Перебор простых делителей +=2 и 235

Вместо $i++ можно поставить $i+=2. Так будет меньше проверяться. Хотя разницы особой не увидел. Также можно проверять не только лишь все числа, а мало какие можно проверять. По-английски это называется wheel factorization. Колесная факторизация дает еще немного секунд.

//for($i=7;$i<$max;$i++)
for($i=7;$i<$max;$i+=2)

//for($i=7;$i<$max;$i++)
$steps[]=2;
$steps[]=6;
$steps[]=4;
$steps[]=2;
$steps[]=4;
$steps[]=2;
$steps[]=4;
$steps[]=6;
for($i=7,$n=1;$i<$max;$i+=$steps[(++$n)%8])

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

Числа 2*2, 2*3, 2*4, …, 3*3, 3*4,… и так далее помечаются как составные. Остальные числа будут простыми. Первый множитель берется как следующее простое число, второй множитель — числа подряд. Википедия.

<?
ini_set('max_execution_time',0);

$max=100_000_000;
$sqrt_max=(int)sqrt($max);

$numbers=str_repeat('1',$max);

$multiplier=2;

$time=time();

while($multiplier<=$sqrt_max)
{
  for($i=$multiplier;$i*$multiplier<$max;$i++)
    $numbers[$i*$multiplier]='0';

  while($numbers[++$multiplier]=='0');
}

echo 'time: ';
echo time()-$time.'<br>';

echo 'memory: ';
echo number_format(memory_get_peak_usage(true)).'<br>';

$primes=0;
for($i=2;$i<strlen($numbers);$i++)
  if($numbers[$i]=='1')$primes++;

echo 'primes/all: '.number_format($primes);
echo ' / '.number_format($max);

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

Описание сложное, можно посмотреть в Википедии.

<?
ini_set('max_execution_time',0);

$max=100_000_000;
$sqrt_max=(int)sqrt($max);

$is_prime=str_repeat('0',$max+1);

$time=time();

$x2=0;
for($i=1;$i<=$sqrt_max;$i++)
{
  $x2+=2*$i-1;
  $y2=0;

  for($j=1;$j<=$sqrt_max;$j++)
  {
    $y2+=2*$j-1;

    $n=4*$x2+$y2;
    if( ($n<=$max) && ($n%12==1 || $n%12==5) )
    {
      if($is_prime[$n]=='0') $is_prime[$n]='1';
      else $is_prime[$n]='0';
    }

    $n-=$x2;
    if( ($n<=$max) && ($n%12==7) )
    {
      if($is_prime[$n]=='0') $is_prime[$n]='1';
      else $is_prime[$n]='0';
    }
    
    $n-=2*$y2;
    if( ($i>$j) && ($n<=$max) && ($n%12==11) )
    {
      if($is_prime[$n]=='0') $is_prime[$n]='1';
      else $is_prime[$n]='0';
    }
  }
}

for($i=5;$i<=$sqrt_max;$i++)
{
  if($is_prime[$i])
  {
    $n=$i*$i;
    for($j=$n;$j<=$max;$j+=$n)
      $is_prime[$j]='0';
  }
}

$primes=3;

for($i=6;$i<$max;$i++)
  if( ($is_prime[$i]=='1') && ($i%3!=0) && ($i%5!=0) )
    $primes++;

echo 'time: ';
echo time()-$time.'<br>';

echo 'memory: ';
echo number_format(memory_get_peak_usage(true)).'<br>';

echo 'primes/all: '.number_format($primes);
echo ' / '.number_format($max);

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

Решето Сундарама простое, оно пусть будет домашним заданием.

Результаты

Простые/все: 664,579 / 10,000,000

Простые/все: 5,761,455 / 100,000,000

Для сравнения: WinRAR/Меню/Операции/Тест быстродействия, без многопоточности =1200.

Литература

Еще раз о поиске простых чисел

Вычисление массивов по алгоритму «решето Эратосфена» можно сделать быстрым и удобным. Для этого следует алгоритм сделать ступенчатым, а результат выдавать порциями.
Ограничивая задачу поиском простых чисел до maxint = 2147483647, приходим к максимально возможному простому делителю в пределах inter=[sqrt(maxint)]=46340.
Имея в распоряжении базовый массив простых чисел в этом диапазоне, можно без труда реализовать алгоритм «решета Эратосфена» на относительно небольших интервалах, в совокупности покрывающих весь диапазон от 0 до maxint.
В свою очередь, для получения базового массива указанного размера нужна таблица простых чисел до [sqrt(inter)]=215.

Программа написана на PHP и содержит следующие функции:

1. base_sieve(), вычисляющая глобальный массив p_base простых чисел в диапазоне от 2 до inter по классическому алгоритму. Каждый множитель p обрабатывает только те элементы решета, которые больше p².
2. main_sieve($from, $to), имеющая выходным параметром массив простых чисел в диапазоне от $from до $to включительно. Обработка решета в диапазоне ведётся только в указанном диапазоне и в обратном порядке, чтобы значение переменной цикла не выходило за пределы maxint. Разные диапазоны обрабатываются независимо.
3. print_p($p, $width), которая выводит числовой массив колонками по $width чисел.

Для тестового примера выбран диапазон в 1001 число, ближайшее к maxint.

Текст программы:

$maxint = 2147483647;
$maxval = 214700000;
$inter = 46340;         // =[sqrt($maxint)]

function print_p($arr, $width){
    print("<br>");
    $prn = $width;
    array_walk($arr, function($item, $key) use(&$prn, $width){
        if ($prn-- == 0){
            print ("<br>");
            $prn = $width-1;
        }
        print $item." ";
    });
    print("<br>");
}

function base_sieve(){
    global $inter, $p_base;
    $p0 = array(    2, 3, 5, 7, 11,             13, 17, 19, 23, 29,         31, 37, 41, 43, 47,         53, 59, 61, 67, 71,
                    73, 79, 83, 89, 97,         101, 103, 107, 109, 113,    127, 131, 137, 139, 149,    151, 157, 163, 167, 173,
                    179, 181, 191, 193, 197,    199, 211, 223);

    $p_sieve = range(0,$inter-1);
    array_walk($p0, function($item) use(&$p_sieve, $inter) {
        for($j=$item*$item; $j<$inter; $j+=$item) $p_sieve[$j] = 0; 
    });
    $p_sieve[1]=0;
    $p_base = array();
    array_walk($p_sieve, function ($item) use(&$p_base){
        if($item) $p_base[]=$item;
    });
}

function main_sieve($from, $to){
    global $maxint, $p_base;
    if(is_int($from) && is_int($to)) $p_sieve = range($from, $to);
    else exit(1);
    array_walk($p_base, function($item) use(&$p_sieve, $from, $to) {
        if($item*$item <= $to) {
            for($j=$to-$to%$item-$from; $j>=max($item*$item-$from,0); $j-=$item) {
                $p_sieve[$j] = 0;               
            }
        }
    });

    $p = array();
    array_walk($p_sieve, function ($item) use(&$p){
        if($item) $p[]=$item;
    });
    return $p;
}

$p_base=0;
base_sieve();
print ("maxint=$maxint inter=$inter");
printf("<br> base_sieve: p_first = %d p_last = %d", reset($p_base), end($p_base));
$p_main = main_sieve($maxint-1000,$maxint);
printf("<br> main_sieve: p_first = %d p_last = %d", reset($p_main), end($p_main));
print_p($p_main,10);

Результаты:

maxint=2147483647 inter=46340
base_sieve: p_first = 2 p_last = 46337
main_sieve: p_first = 2147482661 p_last = 2147483647
2147482661 2147482663 2147482681 2147482693 2147482697 2147482739 2147482763 2147482801 2147482811 2147482817 
2147482819 2147482859 2147482867 2147482873 2147482877 2147482921 2147482937 2147482943 2147482949 2147482951 
2147483029 2147483033 2147483053 2147483059 2147483069 2147483077 2147483123 2147483137 2147483171 2147483179 
2147483237 2147483249 2147483269 2147483323 2147483353 2147483399 2147483423 2147483477 2147483489 2147483497 
2147483543 2147483549 2147483563 2147483579 2147483587 2147483629 2147483647 

Диапазон в 1000000 чисел был обработан программой за 27 секунд на компьютере с индексом производительности 3.5. Увеличение диапазона наталкивается на ограничения по времени и по памяти. В то же время никто не мешает сбрасывать результаты во внешнюю память порциями, что позволяет за несколько часов записать все простые числа до maxint=2³¹-1 включительно.

P.S. Объём внешней памяти для записи результатов можно сильно сэкономить, если использовать полную запись только для первого и последнего (для контроля) чисел на интервале (странице), а внутри писать полуразности. В частности, для последнего вывода получится запись вида 2147482661 1 9 6 2 21 12 ... 2147483647

The best way to check if a number is prime is to see if it is divisible by any prime number before it. Pi(x) is the one I keep seeing everywhere… You can see a bit more information on Prime Counting on wikipedia.

So the most efficient way I can think of at the moment is as follow:

class prime
{
    public $primes = [ 2, 3, 5, 7 ];
    public $not_prime = [ 1, 4, 6, 8, 9 ];
    public function is_prime( int $n )
    {
        if ( $n <= 1 ) return false;
        if ( in_array( $n, $this->primes ) ) return true;
        if ( in_array( $n, $this->not_prime ) ) return false;
        for( $i = 0; $i < count( array_slice( $this->primes, 0, $this->prime_count( $n ) ) ) || $i == $n; $i++ )
        {
            if ( $n % $this->primes[ $i ] == 0 ) return false;
        }
        return true;
    }
    public function build_primes_to( int $n )
    {
        for ( $i = end( $this->primes ) + 1; $i <= $n; $i++ )
        {
            if ( $this->is_prime( $i ) )
            {
                $this->primes[] = $i;
            }
            else
            {
                $this->not_prime[] = $i;
            }
        }
    }
    public function prime_count( $n )
    {
        $ln = log( $n );
        if ( $ln == 0 ) return 1;
        return intval( ceil( $n / $ln ) );
    }
}

Which isn’t actually very efficient, well, not when it comes to building the list of prime numbers… I’ve been working on a better way of building the list here, though it would be just as easy and far more efficient to find a list online and use that.

Usage of the above would be along the lines of:

$find_to = 1000;
$prime = new prime();
$prime->build_primes_to( $find_to );
print "<pre>";
for ( $i = 1; $i < $find_to; $i++ )
{
    print "$i is " . ( !$prime->is_prime( $i ) ? "not " : "" ) . "primen";
}