|
=={{header|PARI/GP}}==
=={{header|PARI/GP}}==
==Version with trial division and fast modular reduction:==
ll.gp
<syntaxhighlight lang="parigp">/* ll(p): input odd prime 'p'. */
/* returns '1' if 2^p-1 is a Mersenne prime. */
{
ll(p) =
my(s = 4, m = 2^p-1, n = m+2, d = 2*p, q = 1, r = exponent(p)+1);
/* do some trial division up to a reasonable depth. */
for(i = 1, (r/4)^r\p,
q += d;
if(Mod(2,q)^p == 1, return)
);
/* Lucas-Lehmer test with fast modular reduction. */
for(i = 3, p,
s = sqr(s);
s = bitand(s,m)+s >> p;
if(s >= m, s -= n, s -= 2)
);
!s
}; /* end ll */</syntaxhighlight>
<syntaxhighlight lang="parigp">
export(ll) /* export ll to the parallel world if parallel processing is enabled */
/* get the first 30 Mersenne primes */
{
t=0;c=1;p=2;gettime();
thr=default(nbthreads);
printf("#%d\tM%d\t%3dh, %2dmin, %2d,%03d ms\n", c, p, t\3600000, t\60000%60, t\1000%60, t%1000);
parforprime(p=3, 132049, ll(p), d, /* ll(p) -> d copy from parallel world into real world. */
if(d,
c++;
t += gettime()\thr;
printf("#%d\tM%d\t%3dh, %2dmin, %2d,%03d ms\n", c, p, t\3600000, t\60000%60, t\1000%60, t%1000)
)
)
};</syntaxhighlight>
{{out}}
Compiled with gp2c option: gp2c-run -g ll.gp.
Done on Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz, 4 hyperthreaded cores.
<pre>#1 M2 0h, 0min, 0,000 ms
#2 M3 0h, 0min, 0,000 ms
#3 M5 0h, 0min, 0,000 ms
#4 M7 0h, 0min, 0,000 ms
#5 M13 0h, 0min, 0,000 ms
#6 M17 0h, 0min, 0,000 ms
#7 M19 0h, 0min, 0,000 ms
#8 M31 0h, 0min, 0,000 ms
#9 M61 0h, 0min, 0,000 ms
#10 M89 0h, 0min, 0,000 ms
#11 M107 0h, 0min, 0,000 ms
#12 M127 0h, 0min, 0,000 ms
#13 M607 0h, 0min, 0,002 ms
#14 M521 0h, 0min, 0,002 ms
#15 M1279 0h, 0min, 0,011 ms
#16 M2203 0h, 0min, 0,040 ms
#17 M2281 0h, 0min, 0,042 ms
#18 M3217 0h, 0min, 0,096 ms
#19 M4253 0h, 0min, 0,191 ms
#20 M4423 0h, 0min, 0,213 ms
#21 M9689 0h, 0min, 1,951 ms
#22 M9941 0h, 0min, 2,187 ms
#23 M11213 0h, 0min, 3,365 ms
#24 M19937 0h, 0min, 29,758 ms
#25 M21701 0h, 0min, 43,233 ms
#26 M23209 0h, 0min, 58,444 ms
#27 M44497 0h, 9min, 41,164 ms
#28 M86243 1h, 17min, 58,437 ms
#29 M110503 3h, 1min, 0,935 ms
#30 M132049 5h, 38min, 45,848 ms
? ##
*** last result: cpu time 44h, 51min, 28,870 ms, real time 5h, 38min, 2,249 ms.
?</pre>
=={{header|Pascal}}==
int64 is good enough up to M31:
|