[PHP] Sito Eratostenesa czyli algorytm do wyznaczania liczb pierwszych

Na prośbę jednego z moich czytelników publikuje implementacje algorytmu sita Eratostenesa w PHP. Poniższy kod generuje listę liczb pierwszych w podanym przez nas zakresie.
Kod:

<?php
$n = 100;
$table = array_fill(2, $n, '');

for($h = 2; ($h * $h) <= $n; ++$h)
{
 for($i = (2 * $h); $i <= $n; $i += $h)
 {
  unset($table[$i]);
 }
}

var_dump($table); // Klucze tablicy są liczbami pierwszymi
?>

Chyba tłumaczenie jest zbędne przy tak małej ilości linijek, prawda?

Jeżeli ktoś potrzebuje sprawdzić pojedynczą liczbę pod kątem tego czy jest liczbą pierwszą to proponuje zrobić to tak:
Kod:

<?php
function is_prime_number($number)
{
 // Tak dla niepoznaki
 if($number < 2)
 {
  return false;
 }

 for($h = 2; $h < $number; ++$h)
 {
  if($number % $h == 0)
  {
   return false;
  }
 }

 return true;
}

$n = 100;
$table = array_fill(2, $n, '');

echo 'Czy liczba pierwsza?<br>';

foreach($table as $key => $value)
{
 echo $key.' - '.(is_prime_number($key) ? 'tak' : 'nie').'<br>';
}

echo '<hr>';
// lub dla pojedynczej pozycji
$try = 666;
echo $try.' - '.(is_prime_number($try) ? 'tak' : 'nie');
?>

Na upartego jeżeli mamy załadowaną odpowiednią bibliotekę (GMP) to możemy skorzystać z funkcji gmp_prob_prime().

Komentarze

• 1

Dodaj komentarz

Zezwolono używać: BBCode
Zabroniono używać: znaczników HTML

Podpis: (Wymagany)

E-mail: (Wymagany, niepublikowany)

Strona WWW: (Nie wymagana)

Token:

Treść tokena: (Przepisz tylko cyfry!)

Treść: (Wymagana)

Tagi

php webmaster webmastering programowanie strony number ciekawostka tutorial porada example artykul skrypt rada projektowanie is algorytm prime sito eratostenesa