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() ;
    }
}

Reply via email to