Eratostenovo sito

U matematici Eratostenovo sito je postupak za određivanje prostih brojeva manjih od nekog zadatog broja n. Kreirao ga je Eratosten, starogrčki matematičar.

Algoritam

1. Napišite sve brojeve od 2 do n
2. Počevši od prvog broja na spisku (dvojka) precrtajte sa spiska sve brojeve deljive sa dva i upišite da je dvojka prost broj.
3. Ponavljajte postupak sa sledećim neprecrtanim brojem m. Dakle, precrtajte sve brojeve deljive sa m, a njega samog obeležite da je prost.

Napomena: Postoje efikasniji algoritmi za proveru da li je neki određeni broj prost. Eratostenovo sito nalazi sve proste brojeve do nekog broja.

Modifikacija

1. Iz razmatranja možemo izbaciti parne brojeve veće od 2 jer su svi oni složeni. Tako je prvi broj čije sadržaoce tražimo 3, a ne 2.
2. b) Postupak precrtavanja brojeva počinjemo od m² jer su svi brojevi manji od m² već izbrisani.
3. b) Čim nađemo prost broj m takav da je m²>n nemamo potrebu za daljim brisanjem. Svi preostali brojevi su prosti!

U programskom jeziku Pascal program bi izgledao :

program Eratosten;
var  A:array[1..100] of integer;
     K:array[1..100] of boolean;
     i,n,x:integer;
begin
   readln(n);
   for i:=2 to n do
   begin
      A[i]:=i;
      K[A[i]]:=true;
   end;
   i:=2;
   while (i*i<=n) do
   begin
      x:=i;
      while (x<n) do
      begin
         x:=x+a[i];
         if (x>=n) then 
         begin
         x:=x-A[i];
         break;
         end;
         K[a[x]]:=false;
      end;
      i:=i+1;
   end;
   for i:=2 to n do
     If K[a[i]]=true then
        writeln(a[i]);
end.

Primer

Želimo da nađemo sve proste brojeve do 120. Napišemo na papir brojeve od 2 do 120.
Dvojka je prost broj. Izbrišemo sve parne brojeve.
Sledeći broj na spisku je trojka. Obeležimo i nju da je prosta. Sa spiska brišemo 9,15,21,27,...
Sledeći broj na spisku je petica. I to je prost broj. Sa spiska brišemo 25,35,55,65,85,95,115
Sledeća nam je na spisku sedmica. U spisku prostih brojeva imamo za sada 2,3,5 i 7. Brišemo sa spiska 49, 77, 91 i 119. Napomena: 56, 63, 70, 84, 98, 105 i 112 su već ranije izbrisani.
Sledeći broj je 11. Kako je 11²>120 to obeležavamo da su svi preostali brojevi prosti. To su 11, 13, 17, 19, 23, 29, 31, 37, ...