/*
 * Задание 4
 * Написать программу для проверки на простоту числа Мерсенна с
 * использование теста Люка-Лемера. С клавиатуры вводится номер числа
 * Мерсенна
 */

#include <iostream>
#include <cmath>

// Тест Люка-Лемера для проверки простоты числа Мерсенна
bool lucasLehmerTest(long long p) {
    if (p == 2) return true; // M_2 = 3, простое число

    // Вычисляем M_p = 2^p - 1
    long long M_p = pow(2, p) - 1;

    std::cout << M_p << std::endl;

    // Начальное значение s
    long long s = 4;

    // Выполняем тест
    for (long long i = 3; i <= p; ++i) {
        s = (s * s - 2) % M_p; // s = s^2 - 2
    }

    // Если s % M_p == 0, то M_p простое
    return s == 0;
}

int main() {
    long long p;
    std::cout << "Введите номер числа Мерсенна (простое число p): ";
    std::cin >> p;

    if (lucasLehmerTest(p)) {
        std::cout << "Число Мерсенна M_" << p << " = 2^" << p << " - 1 является простым." << std::endl;
    } else {
        std::cout << "Число Мерсенна M_" << p << " = 2^" << p << " - 1 не является простым." << std::endl;
    }

    return 0;
}