24 июн 2020 в 18:04

Простые_числа.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.

Литература

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

Хабы: