Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

// "Решето Эратосфена" - вычисление простых чисел
const n = 100000;

var primes: set of integer;

begin
 primes := [2..n];
 
 for var i:=2 to round(sqrt(n)) do
 if i in primes then
 begin
 var x := 2*i;
 while x<=n do
 begin
 Exclude(primes,x);
 x += i;
 end;
 end;

 writeln('Простые числа < ',n,':');
 writeln(primes);
 writeln;
 writeln('Время вычисления: ',Milliseconds/1000);
end.

---

---