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, ...