Eratostenovo sito

Animirano Eratostenovo sito

Eratostenovo sito (rešeto) je jednostavan algoritam za dobivanje svih prostih brojeva manjih od unaprijed izabranoga prirodnog broja. Osmislio ga je grčki matematičar, geograf i astronom Eratosten.

Postupak dobivanja prostih brojeva pomoću Eratostenovog sita:

1. napišemo proizvoljan broj uzastopnih prirodnih brojeva počevši od 2
2. zaokružimo najmanji neoznačeni broj
3. precrtamo sve njegove višekratnike, koji nisu već označeni
4. ponavljamo postupak od 2. koraka dok svi brojevi nisu označeni (zaokruženi ili precrtani)

Postupak završi u konačno mnogo koraka, jer na početku imamo konačno mnogo brojeva, a u svakom koraku barem jedan broj označimo. Zaokruženi brojevi su prosti brojevi. Precrtani brojevi su složeni brojevi.

Na slici je demonstracija traženja prostih brojeva manjih od 121. Napisani su svi prirodni brojevi od 2 do 120. U prvom koraku je najmanji neoznačeni broj 2, zato ga označimo crvenom bojom, a onda nježnijom nijansom crvene boje "precrtamo" ostale njegove višekratnike. Nakon toga je najmanji neoznačeni broj broj 3. Njega "zaokružimo" zelenom, a nježnijom nijansom zelene "precrtamo" višekratnike broja 3. Nakon toga je najmanji neoznačeni broj 5. Njega označimo plavom bojom, a njegove višekratnikom svjetlijom nijansom plave. Isto napravimo s brojem 7. Nakon toga je na redu broj 11. No sve njegove višektratnike smo ionako već precrtali. Zato radi jednostavnosti sve ostale proste brojeve označimo istom bojom, iako to baš nije sasvim korektno.

Iako jako jednostavan, opisani postupak nije baš učinkovit za traženje velikih prostih brojeva. Tek za ilustraciju algoritma je priložen programski kod u programskom jeziku VB.NET:

   Sub Main()
       Dim prost As Integer
       Dim lista As New List(Of Integer)
       'u listu dodaj sve brojeve od 2 do 1000
       For i = 2 To 1000
           lista.Add(i)
       Next
       'ponavljaj sve dok ima brojeva u listi
       While lista.Count > 0
           'ispiši najmanji broj iz liste - to je prosti broj
           prost = lista.Min
           Console.WriteLine(prost)
           'iz liste izbacimo ispisani broj i sve njegove višektranike
           For i = prost To 1000 Step prost
               lista.Remove(i)
           Next
       End While
       Console.ReadLine()
   End Sub

U DELPHIJU: program Izbacivanje; {$APPTYPE CONSOLE} uses

 SysUtils;

var a:array[1..150] of integer;

    ok:array[1..150] of boolean;
    i,n,k:integer;

begin

  writeln('Unesite n ');
  readln(n);
  for i:=2 to n do
  begin
     a[i]:=i;
     ok[a[i]]:=true;
  end;
  i:=2;
  while (i*i<=n) do
  begin
     k:=i;
     while (k<n) do
     begin
        k:=k+a[i];
        ok[a[k]]:=false;
     end;
     i:=i+1;
  end;
  for i:=2 to n do
    If ok[a[i]]=true then
       writeln(a[i]);
  readln;

end.