primzahl.pas

program primzahl;

Uses sysutils, Math;

function ist_primzahl(n: integer): boolean;
var i, j : integer;
    sieb: array of boolean;
    limit : integer;
begin
  limit:=Math.ceil(sqrt(n));
  setlength(Sieb,n);
  for i := 2 to limit do
  begin
    j := 2 * i;
    if Sieb[i] = false then
    begin
      while j <= n do
      begin
        Sieb[j] := true;
        j := j + i;
      end;
    end;
  end;
  ist_primzahl := not Sieb[n];
end;

begin
  if ist_primzahl(12) = true then
    writeln('12 ist eine Primzahl')
  else
    writeln('12 ist keine Primzahl');

  if ist_primzahl(13) = true then
    writeln('13 ist eine Primzahl')
  else
    writeln('13 ist keine Primzahl');
end.