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