primes.pll

一个嵌入式系统的C代码

PROGRAM Primes (OUTPUT);

{--------------------------------------------------------------------}
{ Program to compute Prime Numbers based on a program taken from     }
{ "Programming In MODULA-2" - I knew this thing would come in handy  }
{ some day!  This overly complex algorithm is based on the idea of   }
{ inspecting the divisibility of successive integers.  The tested    }
{ integers are obtained by incrementing alternatly by 2 and 4 which  }
{ avoids multiples of 2 and 3 (which can't be prime).  Divisibility  }
{ only needs be tested for prime divisors, which are obtained by     }
{ storing previously computed resluts (Wirth, N., 1982).             }
{--------------------------------------------------------------------}


CONST
  N = 500;
  M = 23;      { M ~= sqrt(N) }
  L = 04;      { Primes per lime }

VAR
  i, k, x : INTEGER;
  inc, lim, square, cnt : INTEGER;
  prime : INTEGER;
  P, V  : ARRAY [M] OF INTEGER;

BEGIN
  cnt := 0;
  x := 1;
  inc := 4;
  lim := 1;
  square := 9;
  FOR i := 3 TO N DO BEGIN
    REPEAT
      x := X + inc;
      inc := 6 - inc;
      IF square <= x THEN BEGIN
        lim := lim + 1;
        V[lim] := square;
        square := P[lim+1] * P[lim+1]
      END;
      k := 2;
      prime := 1;
      WHILE (prime = 1) AND (k < lim) DO BEGIN
        k := K + 1;
        IF V[k] < x THEN
          V[k] := V[k] + 2 * P[k];
        IF (x <> V[k]) THEN
          prime := 1
        ELSE
          prime := 0
      END
    UNTIL prime = 1;
    IF i <= M THEN
      P[i] := x;
    Write('  ', x#);
    cnt := cnt + 1;
    IF cnt >= L THEN BEGIN
      Writeln;
      cnt := 0
    END
  END;
  Writeln
END.