z5.1.cpp

#include <iostream>
using namespace std;

// Простейшая проверка простоты (перебор до sqrt(n))
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;
}

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

    // Выведем первые N чисел Мерсена (будем считать p = 2,3,5,7,11,...)
    // 1) Найдём первые N простых p
    // 2) Посчитаем 2^p - 1 и проверим, простое или нет
    int countPrimes = 0;
    long long current = 2;
    while(countPrimes < N)
    {
        if (isPrime(current))
        {
            // current - это p
            long long M = 1;
            // Вычисляем 2^p
            for (int i = 0; i < current; i++)
            {
                M *= 2;
            }
            M -= 1; // 2^p - 1

            // Проверим простоту M
            bool primeM = isPrime(M);

            cout << "M(" << current << ") = 2^" << current << " - 1 = " << M;
            if (primeM) cout << " (простое)\n";
            else        cout << " (непростое)\n";

            countPrimes++;
        }
        current++;
    }
    return 0;
}