z5.2.cpp

#include <iostream>
using namespace std;

// Проверка простоты
bool isPrime(long long x)
{
    if (x < 2) return false;
    for (long long i = 2; i*i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

// Возвращает n-ое простое число
long long nthPrime(int n)
{
    int count = 0;
    long long cur = 2;
    while(true)
    {
        if (isPrime(cur))
        {
            count++;
            if (count == n) return cur;
        }
        cur++;
    }
}

// Возвращает 2^p - 1
long long mersenneNumber(long long p)
{
    long long M = 1;
    for (int i = 0; i < p; i++)
        M <<= 1; // побитовое смещение влево (ускоренный способ умножить на 2)
    return M - 1;
}

int main()
{
    int N;
    cout << "Сколько чисел Мерсена вывести? ";
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        long long p = nthPrime(i);
        long long M = mersenneNumber(p);
        cout << "M(" << p << ") = " << M;
        if (isPrime(M)) cout << " (простое)\n";
        else            cout << " (непростое)\n";
    }
    return 0;
}