#include <iostream>
#include <cmath>

using namespace std;

//cette fonction verifie si n est premier
int premier (int);

int main() {
  int mersenne;
  //boucle sur les nombres de Mersenne de 2 a 25
  for (int n=1; n<=25; n++) {
    mersenne = pow(2,n) - 1;
    int reponse = premier (mersenne);  
    if (reponse > 0) cout << "Le " << n << "eme nombre de Mersenne " << mersenne << " est premier" << endl;
    else cout << "Le " << n << "eme nombre de Mersenne " << mersenne << " n'est pas premier" << endl;
  }
   
  return 0;
}

int premier (int n) {
  if (n == 1) return 0;   //1 n'est pas premier
  if (n == 2) return 1;   //2 est premier
  if (n%2 == 0) return 0;   //nombre pair > 2
  //il suffit de verifier tous les impairs < sqrt(n) 
  int nMax = sqrt(double(n));
  for (int i=3; i<=nMax; i+=2)
    if (n%i == 0) return 0;   //j'ai trouve un diviseur
  return 1;
}