Lucas-Lehmer Test:

for 



p


{\displaystyle p}

 an odd prime, the Mersenne number 




2

p


−
1


{\displaystyle 2^{p}-1}

 is prime if and only if 




2

p


−
1


{\displaystyle 2^{p}-1}

 divides 



S
(
p
−
1
)


{\displaystyle S(p-1)}

 where 



S
(
n
+
1
)
=
(
S
(
n
)

)

2


−
2


{\displaystyle S(n+1)=(S(n))^{2}-2}

, and 



S
(
1
)
=
4


{\displaystyle S(1)=4}

.



Task

Calculate all Mersenne primes up to the implementation's
maximum precision, or the 47th Mersenne prime   (whichever comes first).




F isPrime(p)
   I p < 2 | p % 2 == 0
      R p == 2
   L(i) 3..Int(sqrt(p))
      I p % i == 0
         R 0B
   R 1B
 
F isMersennePrime(p)
   I !isPrime(p)
      R 0B
   I p == 2
      R 1B
   V mp = BigInt(2) ^ p - 1
   V s = BigInt(4)
   L 3..p
      s = (s ^ 2 - 2) % mp
   R s == 0
 
L(p) 2..2299
   I isMersennePrime(p)
      print(‘M’p, end' ‘ ’)