informatyki i systemów mikroprocesorowych

Sito Eratostenesa jest sposobem wyznaczania liczb pierwszych zaproponowanym przez greckiego matematyka Eratostenesa. Metoda sita (w założeniu eliminacja) polega na odrzucaniu liczb naturalnych będących wielokrotnościami liczb pierwszych.

Przykład:
Weźmy pod uwagę liczby naturalne z przedziału <2,20> (liczba 1 nie jest liczbą pierwszą więc ją pomijamy - tak stanowi algorytm).

Liczba 2 jest liczbą pierwszą - dokonujemy eliminacji jej wielokrotności:
Pozostają liczby:
2,3,5,7,9,11,13,15,17,19

Kolejna liczba - 3 jest liczbą pierwszą - dokonujemy eliminacji jej wielokrotności:
Pozostają liczby:
2,3,5,7,11,13,17,19

Kolejna liczba - 5 jest liczbą pierwszą - dokonujemy eliminacji jej wielokrotności (brak takich liczb w badanym przedziale):
Pozostają liczby:
2,3,5,7,11,13,17,19

Postępujemy podobnie z nastepnymi liczbami.
W przytoczonym przykładzie już po eliminacji liczby 3 pozostały tylko liczby pierwsze.

Podsumowując:
Dla danej liczby n wszystkie niewyeliminowane liczby mniejsze od n są liczbami pierwszymi.

 

Program (Turbo Pascal)

program Sito_Erastotenesa;
uses crt;
 const
   zakres = 50;
 var
   sito : array [2..zakres] of boolean;
   i,j : longint;
 begin
   clrscr;
   for i:= 2 to zakres do sito [i] := true;
   for i:= 2 to zakres do  
     if sito [i] then 
        begin
           writeln (i);     
           j:= 2;
           while i*j<=zakres do
              begin
                 sito [i*j] := false;
                 j:=j+1;
              end;
        end;
  repeat until keypressed;
 end.