Lucas-Lehmer test: Difference between revisions
C++ version
m (→{{header|C}}: not that this program needs to be optimised any, but...) |
(C++ version) |
||
Line 136:
M2 M3 M5 M7 M13 M17 M19 M31
=={{header|C++}}==
{{libheader|GMP}}
<pre>#include <iostream>
#include <gmpxx.h>
mpz_class pow2(mpz_class exp);
bool is_mersenne_prime(mpz_class p);
int main()
{
mpz_class maxcount(45);
mpz_class found(0);
mpz_class check(0);
for( mpz_nextprime(check.get_mpz_t(), check.get_mpz_t());
found < maxcount;
mpz_nextprime(check.get_mpz_t(), check.get_mpz_t()))
{
//std::cout << "P" << check << " " << std::flush;
if( is_mersenne_prime(check) )
{
++found;
std::cout << "M" << check << " " << std::flush;
}
}
}
bool is_mersenne_prime(mpz_class p)
{
if( 2 == p )
return true;
else
{
mpz_class div = pow2(p) - mpz_class(1);
mpz_class s(4);
for( mpz_class i(3);
i <= p;
++i )
{
s = (s * s - mpz_class(2)) % div ;
}
return ( s == mpz_class(0) );
}
}
mpz_class pow2(mpz_class exp)
{
// Unfortunately, GMP doesn't have a left-shift method.
// It also doesn't have a pow() equivalent that takes arbitrary-precision exponents.
// So we have to do it the hard (and presumably slow) way.
mpz_class ret(2);
for(mpz_class i(1); i < exp; ++i)
ret *= mpz_class(2);
//std::cout << "pow2( " << exp << " ) = " << ret << std::endl;
return ret;
}
</pre>
Output: (Incomplete; It takes a long time.)
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941
=={{header|Java}}==
We use arbitrary-precision integers in order to be able to test any arbitrary prime.
| |||