Please see source in attachment. The output is 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
It missed 2 Mersenne Primes 9689 & 21701. Is it my program bug or bigint broken? It seems subtle. Thank you!
import std.stdio, std.math, std.bigint; bool isPrime(int p) { if(p < 2 || p % 2 == 0) return p == 2 ; foreach( i ; 3..cast(uint)(sqrt(p)) + 1) if(p % i == 0) return false ; return true ; } bool isMersennePrime(int p) { if(!isPrime(p)) return false ; if(p == 2) return true ; auto mp = (BigInt(1) << p) - 1 ; auto s = BigInt(4) ; foreach(_ ; 3..p+1) s = (s*s - 2) % mp ; return s == 0 ; } shared int[] result ; void main() { auto mp = [9689, 9941, 11213, 19937, 21701, 23209] ; foreach(p ; 0..9689) if(isMersennePrime(p)) { write(" M", p) ; stdout.flush() ; } foreach(p ; mp) { if(isMersennePrime(p)) write(" M", p) ; else writeln("\n*** M", p, "***") ; stdout.flush() ; } }