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, ...
| 2 | 3 | 5 | 7 | 9 | |||||
| 11 | 13 | 15 | 17 | 19 | |||||
| 21 | 23 | 25 | 27 | 29 | |||||
| 31 | 33 | 35 | 37 | 39 | |||||
| 41 | 43 | 45 | 47 | 49 | |||||
| 51 | 53 | 55 | 57 | 59 |
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.
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 25 | 29 | |||||||
| 31 | 35 | 37 | |||||||
| 41 | 43 | 47 | 49 | ||||||
| 53 | 55 | 59 |
Według tej samej procedury postępujemy dla liczby 5.
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 | ||||||||
| 31 | 37 | ||||||||
| 41 | 43 | 47 | 49 | ||||||
| 53 | 59 |
Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 | ||||||||
| 31 | 37 | ||||||||
| 41 | 43 | 47 | |||||||
| 53 | 59 |
Dla danej liczby n wszystkie niewykreślone liczby mniejsze od n są liczbami pierwszymi.
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 | ||||||||
| 31 | 37 | ||||||||
| 41 | 43 | 47 | |||||||
| 53 | 59 |
Spis treści |
[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 />';
}
}// Edzior!
?>
