mersenne.cpp

// g++ -O3 -Wall -o mersenne mersenne.cpp --std=c++14 -lgmp -lpthread
#include <iostream>
#include <vector>
#include <future>
#include <boost/multiprecision/gmp.hpp>

using namespace boost::multiprecision;

// returns 2^exp - 1
mpz_int power(const uint64_t exp)
{
    mpz_int number = 2;
    for (uint64_t i = 1; i < exp; ++i) {
        number *= 2;
    }

    number--;

    return number;
}

// Performs LL test for exp if exp is odd
bool lucas_lehmer(uint64_t exp)
{
    uint64_t res = exp;

    // corner cases
    if (exp == 2) {
        std::cout << "M" << res << " " << std::flush;
        return true;
    }
    else if (exp%2 == 0) return false;

    // main calc
    mpz_int s = 4;
    mpz_int number = power(exp);

    while (exp > 2) {
        s = (s*s - 2) % number;
        exp--;
    }

    if (s == 0) {
        std::cout << "M" << res << " " << std::flush;
        return true;
    }
    else return false;
}

auto async_worker(const uint64_t n)
{
    std::vector<std::future<bool>> fut;
    fut.reserve(n);

    for (uint64_t i = 1; i<=n; ++i) {
        fut.push_back(std::async(lucas_lehmer, i));
    }

    return fut;
}


int main(int argc, char* argv[])
{
    uint64_t n = 43112609;
    if (argc > 1) n = std::stoul(argv[1]);

    auto vec = async_worker(n);

    for (auto& i: vec) {
        i.get();
    }


    return 0;
}