46 lines
1.4 KiB
C++
46 lines
1.4 KiB
C++
/*
|
||
* Задание 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;
|
||
}
|
||
|