Lucas-Lehmer test

Lucas-Lehmer test
You are encouraged to solve this task according to the task description, using any language you may know.

Lucas-Lehmer Test: for p a prime, the Mersenne number 2**p-1 is prime if and only if 2**p-1 divides S(p-1) where S(n+1)=S(n)**2-2, and S(1)=4.

The following programs calculate the first 45 Mersenne primes.

ALGOL 68

main:(
  PR precision=6800 PR

  PROC is prime = ( INT p )BOOL:
    IF p = 2 THEN TRUE
    ELIF p <= 1 OR p MOD 2 = 0 THEN FALSE
    ELSE
      BOOL prime := TRUE;
      FOR i FROM 3 BY 2 TO ENTIER sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD;
      prime
    FI;

  PROC is mersenne prime = ( INT p )BOOL:
    IF p = 2 THEN TRUE
    ELSE
      LONG LONG INT m p =  LONG LONG 2 ** p - 1, LONG LONG INT s := 4;
      FROM 3 TO p DO
        s := (s * s - 2) MOD m p
      OD;
      s = 0
    FI;

  printf($" Mersenne primes: "l$);
  INT upb = ROUND(log(10)/log(2)*10 000 000);
  FOR p FROM 2 TO upb DO
    IF is prime(p) THEN
      IF is mersenne prime(p) THEN
        printf (($" M"g(0)$,p))
      FI
    FI
  OD
)

Output:

Mersenne primes: 
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281
M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209 M44497 M86243
M110503 M132049 M216091 M756839 M859433 M1257787 M1398269 M2976221 M3021377 
M6972593 M13466917 M20996011 M24036583 M25964951 M30402457 M32582657 M33219281

See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html