Ератостеново сито

У математици Ератостеново сито је поступак за одређивање простих бројева мањих од неког задатог броја n. Креирао га је Ератостен, старогрчки математичар.

Алгоритам

1. Напишите све бројеве од 2 до n
2. Почевши од првог броја на списку (двојка) прецртајте са списка све бројеве дељиве са два и упишите да је двојка прост број.
3. Понављајте поступак са следећим непрецртаним бројем m. Дакле, прецртајте све бројеве дељиве са m, а њега самог обележите да је прост.

Напомена: Постоје ефикаснији алгоритми за проверу да ли је неки одређени број прост. Ератостеново сито налази све просте бројеве до неког броја.

Модификација

1. Из разматрања можемо избацити парне бројеве веће од 2 јер су сви они сложени. Тако је први број чије садржаоце тражимо 3, а не 2.
2. б) Поступак прецртавања бројева почињемо од m² јер су сви бројеви мањи од m² већ избрисани.
3. б) Чим нађемо прост број m такав да је m²>n немамо потребу за даљим брисањем. Сви преостали бројеви су прости!

У програмском језику Pascal програм би изгледао :

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.

Пример

Желимо да нађемо све просте бројеве до 120. Напишемо на папир бројеве од 2 до 120.
Двојка је прост број. Избришемо све парне бројеве.
Следећи број на списку је тројка. Обележимо и њу да је проста. Са списка бришемо 9,15,21,27,...
Следећи број на списку је петица. И то је прост број. Са списка бришемо 25,35,55,65,85,95,115
Следећа нам је на списку седмица. У списку простих бројева имамо за сада 2,3,5 и 7. Бришемо са списка 49, 77, 91 и 119. Напомена: 56, 63, 70, 84, 98, 105 и 112 су већ раније избрисани.
Следећи број је 11. Како је 11²>120 то обележавамо да су сви преостали бројеви прости. То су 11, 13, 17, 19, 23, 29, 31, 37, ...