Eratosthenes.pas

Denna kod är public domain. Om ni hittar fel eller vill ändra något i koden blir jag jätteglad om ni skickar dessa ändringar till jesper [at] fantasi [punkt] se.

(* Eratosthenes såll är en gammal grekisk algoritm som hittar alla primtal
 * upp till en given gräns.
 *)
program Eratosthenes;

const limit = 20000;

var count         : integer;
    i, k          : integer;
    prime         : integer;
    maxsize       : integer;
    markNonPrimes : boolean;
    flags         : array[0..limit] of boolean;

begin
   Write('Ange övre gräns (max ', limit, '): ');
   Readln(maxsize);
   if maxsize > limit then begin
      Writeln('Jag vill inte räkna längre än till ', limit, '.');
      maxsize := limit;
   end;
   Writeln;
   Writeln('I intervallet 3 .. ', maxsize, ' finns följande primtal:');
   Writeln('-----------------------------------------------');

   maxsize := (maxsize - 1) div 2;
   count := 0;
   markNonPrimes := true;
   for i := 0 to maxsize do
      flags[i] := true;

   for i := 1 to maxsize do
      if flags[i] then begin
         prime := i + i + 1;
         Write(prime:8);
         count := count + 1;
         if markNonPrimes then begin
            k := (i + i) * (i + 1);
            if (k > maxsize) or (k < 0) then
               markNonPrimes := false
            else
               while (k <= maxsize) and (k > 0) do begin
                  flags[k] := false;
                  k := k + prime;
               end;
         end;
      end;
   Writeln;
   Writeln;
   Writeln('Totalt ', count, ' primtal.');
end.