Простые_числа.php

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



Подготовка


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

php7.bat
php -S localhost:80 -t localhost

php.ini
[PHP]
memory_limit = 12G


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


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


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

prime.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. Колесная факторизация дает еще немного секунд.

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


prime.php 235
//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,… и так далее помечаются как составные. Остальные числа будут простыми. Первый множитель берется как следующее простое число, второй множитель — числа подряд. Википедия.

erat.php
<?
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);


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


Описание сложное, можно посмотреть в Википедии.
atkin.php
<?
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
Алгоритм Время Память
Деление 13 56,623,104
Эратосфен 1 12,582,912
Аткин 3 12,582,912
Простые/все: 5,761,455 / 100,000,000
Алгоритм Время Память
Деление 267 408,944,640
Деление +=2 260 408,944,640
Деление 235 257 408,944,640
Эратосфен 9 102,760,448
Аткин 26 102,760,448
Для сравнения: WinRAR/Меню/Операции/Тест быстродействия, без многопоточности =1200.

Литература


Еще раз о поиске простых чисел
Tags:
простые числа, решето Эратосфена, решето Аткина

You can't comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author's username will be hidden by an alias.