program primzahlen;
{Stellt alle Primzahlen dar, ziemlich effizienter Algorithmus
Gerade Zahlen gleich ausgeschlossen und Endziffer 5, pr�ft, ob Quersumme durch 3 teilbar
Pr�ft, ob Quadratzahl, Im letzten šberpr�fungsalgoritmus(for k:=1 to anz)
wird gepr�ft ob Zahl durch gespeicherte Primzahlen teilbar ist(vielfache einer Primzahl machen keinen Sinn)}

uses crt;

const size = 16100;

type zahltyp = longint;

var i, k, fehler, anz, wurzel, pos : zahltyp;
    z, zeile                       : byte;
    bool, weiter                   : boolean;
    primfeld                       : array[1..size] of zahltyp;
    outfile                        : text;

function primzahl(pz: zahltyp) : boolean;
  var j, r : zahltyp;
  begin
    j:=0;
    repeat
      j:=j+1;
      if pz mod j = 0 then r:=j;
    until (r>1) or (r=pz);
    if r=pz then primzahl:=true
            else primzahl:=false;
    if pz=1 then primzahl:=true;
  end;

function quersumme(zahl: zahltyp): byte;
  var zs       : string;
      qs, j    : byte;
      zi, code : integer;
  begin
    str(zahl, zs);
    qs:=0;
    for j:=1 to length(zs) do
      begin
        val(zs[j], zi, code);
        qs:=qs+zi;
      end;
    quersumme:=qs;
  end;

begin
  clrscr;
  assign(outfile, 'przahl_1.txt');
  rewrite(outfile);
  fehler:=0;
  pos:=0; anz:=0;
  for i:=1 to size do primfeld[i]:=1;
  write(outfile, 1:7);
  zeile:=1;
  {zeile:=0;   fals 1 keine Primzahl}
  for i:=2 to maxint*maxint do
    begin
      z:=i mod 10;
      wurzel := round(sqrt(i));
      bool:=true;
      if (i > 10) then bool:=(z=1) or (z=3) or (z=7) or (z=9);
      {bool:=bool and (quersumme(i) mod 3 > 0) or (i=3);  getestet bei mod 3}
      bool:=bool and (sqrt(i)<>wurzel);
      k:=1; weiter:=true;
      if (i>2) and (bool) then
        while weiter do
          begin
            if (primfeld[k] > wurzel+1)  then weiter:=false;
            if (i mod primfeld[k]) = 0 then
              begin
                bool:=false;
                weiter:=false;
              end
            else inc(k);
            if (k > pos) then weiter:=false;
          end;
      if bool then
        begin
          write(outfile, i:7);
          inc(zeile);
          if (zeile >= 11) then begin
                                  writeln(outfile);
                                  zeile:=0;
                                end;
          if pos < size then inc(pos);
          primfeld[pos]:=i;
          inc(anz);
        end;
      textcolor(7);
      if (i mod 1000) = 0 then writeln(i);
      if keypressed then i:=MAXINT*MAXINT;
    end;
  writeln(outfile);
  write(outfile, anz+1, ' ', fehler); {1 ist auch Primzahl}
  close(outfile);
  readln;
end.