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

У математици Ератостеново сито је поступак за одређивање простих бројева мањих од неког задатог броја 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, ...