Sito Eratostenesa

Z Wikipedii

Sito Eratostenesa to algorytm kolejnego wybierania liczb pierwszych z ciągu liczb naturalnych.

Ze zbioru liczb naturalnych większych od jedności, tj. {2, 3, 4, ...}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4, 6, 8, ...

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6, 9, 12, ..., przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

Według tej samej procedury postępujemy dla liczby 5.

Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

Dla danej liczby n wszystkie niewykreślone liczby mniejsze od n są liczbami pierwszymi.

[edytuj] Animacja

Poniższa animacja w poglądowy sposób przedstawia opisaną procedurę (niem. Primzahlen: liczby pierwsze):

[edytuj] Implementacja w języku Haskell

-- primes jest nieskończoną listą liczb pierwszych. By pobrać pierwszych sto, piszemy: "take 100 primes".
primes = sieve [2..]
    where sieve (p:rest) = p : sieve [n | n <- rest, n `mod` p /= 0]

[edytuj] Implementacja w języku Pascal

program sito_eratostenesa;
uses crt;
 
var
  n,i,j:Integer;
  tab: array[1..100] of Boolean;
 
begin
  Write('Podaj liczbe naturalna od 1 do 100: ');
  readln(n);
  for i:=1 to n do tab[i]:=TRUE;
  for i:=2 to (n+1) div 2 do
    if tab[i] then 
      for j:=2 to (n div i) do
        tab[i*j]:=FALSE;
  Writeln('Oto kolejne liczby pierwsze z przedzialu [1,',n,']');
  for i:=2 to n do
     if (tab[i]) then
       Write(i,',');
  readkey;
end.

[edytuj] Implementacja w języku PHP

<?php
$max = 100; //szukana największa liczba pierwsza
$arr = range( 2, $max );
for( $i = 2; $i < $max; $i++)
{
    if ( $arr[$i] != 0 )
    {
        for( $j = $i + 1; $j < $max; $j++ )
        {
            if( $arr[$j] % $i == 0 )
            {
                $arr[$j] = 0;
            }
        }
    }
}
 
foreach( $arr as $val )
{
    if( $val != 0 )
    {
        echo $val . '<br />';
    }
}
?>

[edytuj] Zobacz też

• Sito Atkina
• Eratostenes,
• przegląd zagadnień z zakresu matematyki.

[edytuj] Linki zewnętrzne

• Animacja sita Eratostenesa