Lucas_Lehmer (C++)

The Lucas-Lehmer test is a primality test used specifically to determine whether a Mersenne number is prime. You can see all the Mersenne Primes here

This code checks. Include the -lgmp to compile it. Try 19 first.

Its a hyper-efficient checking mechanism that the Greater Internet Mersenne Prime Search uses. Without it we wouldn't have the computation to check.

g++ -o lucas lucas.cpp -lgmp 

#include <iostream>  // Add this for std::cout, std::cin, and std::endl
#include <gmp.h>

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i <= n / i; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

bool lucas_lehmer_test(int p) {
    if (p == 2) return true; // 2^2 - 1 = 3 is a Mersenne prime
    if (!is_prime(p)) return false; // If p is not prime, 2^p - 1 is not a Mersenne prime

    mpz_t s;
    mpz_init_set_ui(s, 4); // Initialize s to 4
    mpz_t M;
    mpz_init(M);
    mpz_ui_pow_ui(M, 2, p); // M = 2^p
    mpz_sub_ui(M, M, 1); // M = M - 1, so M = 2^p - 1

    for (int i = 0; i < p - 2; i++) {
        mpz_pow_ui(s, s, 2); // s = s^2
        mpz_sub_ui(s, s, 2); // s = s - 2
        mpz_mod(s, s, M); // s = s mod M
    }

    // If s == 0 then 2^p - 1 is prime
    bool is_mersenne_prime = (mpz_cmp_ui(s, 0) == 0);

    // Clear the mpz_t variables
    mpz_clear(s);
    mpz_clear(M);

    return is_mersenne_prime;
}

int main() {
    int p;
    std::cout << "Enter a prime number p to test if 2^p - 1 is a Mersenne prime: ";
    std::cin >> p;

    bool result = lucas_lehmer_test(p);
    if (result) {
        std::cout << "2^" << p << " - 1 is a Mersenne prime." << std::endl;
    } else {
        std::cout << "2^" << p << " - 1 is not a Mersenne prime." << std::endl;
    }

    return 0;
}