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