Artykuły na każdy temat

[PHP] Sito Eratostenesa czyli algorytm do wyznaczania liczb pierwszych

Dodano 03.06.2012r. o 20:26
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 = ($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

Publikowane komentarze są prywatnymi opiniami użytkowników serwisu. Serwis nie ponosi odpowiedzialności za treść opinii. W trosce o zachowanie poziomu dyskusji wszystkie komentarze podlegają akceptacji przed ich publikacją dlatego proszę cierpliwie czekać aż komentarz zostanie opublikowany.

Julian Pszczołowski

Dodano 08.06.2012r. o 22:07
Sito to fajna rzecz, ale można je jeszcze zoptymalizować: Smile
w linijce for($i = (2 * $h); $i <= $n; $i += $h)
zmienić $i = (2 * $h) na $i = ($h * $h);

oraz: jeśli $h jest już wymazane jako liczba złożona, to nie wymazujemy wielokrotności $h Smile

Dodaj komentarz

Zostaw komentarz jeżeli możesz! Nie bądź przysłowiowym botem! Nie bądź obojętny! Ciebie to nic nie kosztuje, a mi sprawi uśmiech na twarzy.
Zezwolono używać: BBCode
Zabroniono używać:
znaczników HTML

(Wymagany)

(Wymagany, niepublikowany)

(Nie wymagana)

Token:

Obrazek dla bota

(Przepisz tylko cyfry!)

(Wymagana)