Генератор простих чисел за решетом Ератосфена На мові Pascal

Генератор простих чисел за решетом Ератосфена

На мові Pascal

var

a : array [1..5000] of boolean;

n,x,y : integer;

begin

write('n=');readln(n);

a[1] := false;

for x:=2 to N do a[x] := true;

for x:= 2 to N div 2{round(sqrt(N))} do

for y:= 2 to N div x do

a[x*y] := false;

for x:=1 to N do

if a[x] then write(x,' ');

readln;

end.

Для оптимізації решета Ератосфена можна перебирати тільки непарні числа

Алгоритм записаний на псевдокоді

для i := 2, 3, 4, ..., пока i² ≤ n:

  если A[i] = true:

    для j := i², i² + i, i² + 2i, ..., пока j ≤ n:

      A[j] := false

Выход: числа i, для которых A[i] = true.

Генератор простих чисел за решетом Аткіна

program atkin;

var is_prime:array[1..10001] of boolean; jj:int64;

procedure dosieve(limit:int64);

var i,k,x,y:int64; n:int64;

begin

  for i:=5 to limit do

    is_prime[i]:=false;

  for x:=1 to trunc(sqrt(limit)) do

    for y:=1 to trunc(sqrt(limit)) do

    begin

      n:=4*sqr(x)+sqr(y);

      if (n<=limit) and ((n mod 12 = 1) or (n mod 12 = 5)) then

        is_prime[n]:=not is_prime[n];

      n:=n-sqr(x);

      if (n<=limit) and (n mod 12 = 7) then

        is_prime[n]:=not is_prime[n];

      n:=n-2*sqr(y);

      if (x>y) and (n<=limit) and (n mod 12 = 11) then

        is_prime[n]:=not is_prime[n];

    end;

  for i:=5 to trunc(sqrt(limit)) do

  begin

    if is_prime[i] then

    begin

      k:=sqr(i);

      n:=k;

      while n<=limit do

      begin

        is_prime[n]:=false;

        n:=n+k;

      end;

    end;

  end;

  is_prime[2]:=true;

  is_prime[3]:=true;

end;

begin

  dosieve(10000);

  for jj:=1 to 10000 do

    if is_prime[jj] then

      writeln(jj);

end.