Mersenne primes: Difference between revisions
m
Fixed minor typo
m (Fixed minor typo) |
|||
| (36 intermediate revisions by 19 users not shown) | |||
Line 1:
{{draft task|Prime Numbers}}
;Task:
Create code that will list (preferably calculate) all of the ''Mersenne primes'' until some limitation is reached.
The number of ''known'' Mersenne primes is '''51''' (as of June, 2020), and the largest known Mersenne prime contains contains '''24,862,048''' decimal digits.
;Also see:
* the Wikipedia entry: [https://en.wikipedia.org/wiki/Mersenne_prime Mersenne prime].
* the MathWorld entry; [https://mathworld.wolfram.com/MersennePrime.html Mersenne prime].
* For a list of all the know Mersenne primes: [https://primes.utm.edu/mersenne/index.html#known list of Mersenne
* For a general website about primes: [https://primes.utm.edu/ prime pages].
* the OEIS entry: [https://oeis.org/wiki/Mersenne_primes Mersenne primes].
* the OEIS entry: [https://oeis.org/A000043 A000043 Mersenne exponents: primes p such that 2^p - 1 is prime. Then 2^p - 1 is called a Mersenne prime].
<br><br>
Line 16 ⟶ 20:
{{trans|D}}
<
I bi < 2 {R 0B}
I bi % 2 == 0 {R bi == 2}
Line 36 ⟶ 40:
I is_prime(base - 1)
print(‘2 ^ ’p‘ - 1’)
base *= 2</
{{out}}
Line 48 ⟶ 52:
2 ^ 19 - 1
2 ^ 31 - 1
</pre>
=={{header|ALGOL 60}}==
{{works with|A60}}
<syntaxhighlight lang="ALGOL">
begin
integer procedure mersenne(n);
value n; integer n;
begin
integer i, m;
m := 1;
for i := 1 step 1 until n do
m := m * 2;
mersenne := m - 1;
end;
boolean procedure isprime(n);
value n; integer n;
begin
if n < 2 then
isprime := false
else if entier(n / 2) * 2 = n then
isprime := (n = 2)
else
begin
comment - check odd divisors up to sqrt(n);
integer i, limit;
boolean divisible;
i := 3;
limit := entier(sqrt(n));
divisible := false;
for i := i while i <= limit and not divisible do
begin
if entier(n / i) * i = n then
divisible := true;
i := i + 2
end;
isprime := if divisible then false else true;
end;
end;
comment - main code begins here;
integer i, m;
outstring(1,"Searching to M(31) for Mersenne primes\n");
for i := 1 step 1 until 31 do
begin
m := mersenne(i);
if isprime(m) then
begin
outstring(1,"M(");
outinteger(1,i);
outstring(1,") : ");
outinteger(1,m);
outstring(1,"\n");
end;
end;
end
</syntaxhighlight>
{{out}}
<pre>
Searching to M(31) for Mersenne primes
M( 2 ) : 3
M( 3 ) : 7
M( 5 ) : 31
M( 7 ) : 127
M( 13 ) : 8191
M( 17 ) : 131071
M( 19 ) : 524287
M( 31 ) : 2147483647
</pre>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<syntaxhighlight lang="algol68">
BEGIN # find some Mersenne Primrs - primes of the form 2^n - 1, n must be prime #
# This assumes LONG INT is at least 64 bits (as in e.g. Algol 68G) #
# we handle 2 as a special case and then the odd numbers starting at 3 #
PR read "primes.incl.a68" PR # include prime utilities #
# 2^0 - 1 = 0 and 2^1 - 1 = 1, neither of which is prime #
# start from 2^2 #
INT n := 2;
LONG INT p2 := 4;
IF is probably prime( p2 - 1 ) THEN print( ( " ", whole( n, 0 ) ) ) FI;
# 2^3, 2^5, etc. #
n +:= 1;
p2 *:= 2;
WHILE n < 61 DO
IF is probably prime( p2 - 1 ) THEN print( ( " ", whole( n, 0 ) ) ) FI;
n +:= 2;
p2 *:= 4
OD;
IF is probably prime( p2 - 1 ) THEN print( ( " ", whole( n, 0 ) ) ) FI
END
</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 13 17 19 31 61
</pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw">
begin % find some Mersenne Primrs - primes of the form 2^n - 1, n must be prime %
% integers are 32 bit in Algol W, so there won't be many numbers to check %
% we handle 2 as a special case and then the odd numbers starting at 3 %
% simplified primality by trial division test - no need to check for even %
% numbers as 2^n - 1 is always odd for n >= 2 %
logical procedure oddOnlyPrimalityTest ( integer value n ) ;
begin
logical isPrime;
isPrime := true;
for i := 3 step 2 until entier( sqrt( n ) ) do begin;
isPrime := n rem i not = 0;
if not isPrime then goto endPrimalityTest
end for_i;
endPrimalityTest: isPrime
end oddOnlyPrimalityTest ;
integer p2, n;
n := 1;
p2 := 2;
while
begin
if n < 3 then begin
n := n + 1;
p2 := p2 * 2
end
else begin
n := n + 2;
p2 := p2 * 4
end if_n_le_3__ ;;
if oddOnlyPrimalityTest( p2 - 1 ) then writeon( i_w := 1, s_w := 0, " ", n );
n < 29
end
do begin end ;
% MAXINTEGER is 2**31 - 1 %
if oddOnlyPrimalityTest( MAXINTEGER ) then writeon( i_w := 1, s_w := 0, " ", 31 );
end.
</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 13 17 19 31
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">
on isPrime(integ)
set isComposite to ""
Line 87 ⟶ 238:
set x to x + 1
end repeat
</syntaxhighlight>
----
Or more efficiently:
<syntaxhighlight lang="applescript">on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
set {i, max} to {5, (n ^ 0.5) div 1}
repeat until (i > max)
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
set i to i + 6
end repeat
return true
end isPrime
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on mersennePrimes()
set output to {"Mersenne primes within AppleScript's number precision:"}
-- Special-case 2 ^ 2 - 1.
set end of output to "2 ^ 2 - 1 = 3"
set p to 1 -- Otherwise test odd-numbered powers of 2.
try -- Survive the "numeric operation too large" error when it occurs.
repeat
set p to p + 2
if ((isPrime(p)) and (isPrime(2 ^ p - 1))) then ¬
set end of output to "2 ^ " & p & " - 1 = " & (2 ^ p div 1 - 1)
end repeat
end try
return join(output, linefeed)
end mersennePrimes
mersennePrimes()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"Mersenne primes within AppleScript's number precision:
2 ^ 2 - 1 = 3
2 ^ 3 - 1 = 7
2 ^ 5 - 1 = 31
2 ^ 7 - 1 = 127
2 ^ 13 - 1 = 8191
2 ^ 17 - 1 = 131071
2 ^ 19 - 1 = 524287
2 ^ 31 - 1 = 2.147483647E+9"</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">mersenne?: function [n][
prime? dec 2 ^ n
]
1..31 | select => mersenne?
| loop 'x -> print ["M (" x ") = 2 ^" x " - 1 =" (2^x)-1 "is a prime"]</syntaxhighlight>
{{out}}
<pre>M ( 2 ) = 2 ^ 2 - 1 = 3 is a prime
M ( 3 ) = 2 ^ 3 - 1 = 7 is a prime
M ( 5 ) = 2 ^ 5 - 1 = 31 is a prime
M ( 7 ) = 2 ^ 7 - 1 = 127 is a prime
M ( 13 ) = 2 ^ 13 - 1 = 8191 is a prime
M ( 17 ) = 2 ^ 17 - 1 = 131071 is a prime
M ( 19 ) = 2 ^ 19 - 1 = 524287 is a prime
M ( 31 ) = 2 ^ 31 - 1 = 2147483647 is a prime</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK --bignum -f MERSENNE_PRIMES.AWK
BEGIN {
Line 115 ⟶ 334:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 128 ⟶ 347:
2 ^ 61 - 1
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">m = 0
while True
m += 1
if isPrime((2^m)-1) = True then print m
end while
end
function isPrime(v)
if v <= 1 then return False
for i = 2 To int(sqr(v))
if v % i = 0 then return False
next i
return True
end function</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">Function isPrime(Byval ValorEval As Integer) As Boolean
If ValorEval <= 1 Then Return False
For i As Integer = 2 To Int(Sqr(ValorEval))
If ValorEval Mod i = 0 Then Return False
Next i
Return True
End Function
Dim As Integer m = 0
While True
m += 1
If isPrime((2^m)-1) Then Print m
Wend
Sleep</syntaxhighlight>
{{out}}
<pre>2
3
5
7
13
17
19
31</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">m = 0
while True
m = m + 1
if isPrime((2^m)-1) = True then print m : fi
wend
end
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
end while
return True
end sub</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
=={{header|C}}==
<
#include <stdint.h>
#include <stdio.h>
Line 164 ⟶ 455:
return 0;
}</
{{out}}
<pre>2 ^ 2 - 1
Line 174 ⟶ 465:
2 ^ 19 - 1
2 ^ 31 - 1</pre>
{{libheader|GMP}}
Alternatively, we can use GMP to find the first 23 Mersenne primes in about the same time as the corresponding Wren entry.
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <gmp.h>
#define MAX 23
bool isPrime(uint64_t n) {
uint64_t test;
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
test = 5;
while (test * test < n) {
if (n % test == 0) return false;
test += 2;
if (n % test == 0) return false;
test += 4;
}
return true;
}
int main() {
uint64_t p = 2;
int count = 0;
mpz_t m, one;
mpz_init(m);
mpz_init_set_ui(one, 1);
while (true) {
mpz_mul_2exp(m, one, p);
mpz_sub_ui(m, m, 1);
if (mpz_probab_prime_p(m, 15) > 0) {
printf("2 ^ %ld - 1\n", p);
if (++count == MAX) break;
}
while (true) {
p = (p > 2) ? p + 2 : 3;
if (isPrime(p)) break;
}
}
mpz_clear(m);
mpz_clear(one);
return 0;
} </syntaxhighlight>
{{out}}
<pre>
Same as Wren example.
</pre>
=={{header|C++}}==
{{trans|C}}
<
bool isPrime(uint64_t n) {
Line 206 ⟶ 550:
return 0;
}</
{{out}}
<pre>2 ^ 2 - 1
Line 219 ⟶ 563:
=={{header|C sharp|C#}}==
Needs a better primality checking algorithm to do really large prime numbers.
<
using System.Numerics;
Line 277 ⟶ 621:
}
}
}</
{{out}}
<pre>2 ^ 2 - 1
Line 291 ⟶ 635:
=={{header|D}}==
Simplest thing that could possibly work. Using better primality tests will allow for more results to be calculated in a reasonable amount of time.
<
import std.stdio;
Line 319 ⟶ 663:
base *= 2;
}
}</
{{out}}
<pre>2 ^ 2 - 1
Line 330 ⟶ 674:
2 ^ 31 - 1</pre>
=={{header|
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
procedure MersennePrimes(Memo: TMemo);
var N: integer;
var Mn: int64;
begin
Memo.Lines.Add('2^N-1 Prime');
Memo.Lines.Add('--------------------' );
for N:=1 to 32 do
begin
Mn:=(1 shl N)-1;
if IsPrime(Mn) then
Memo.Lines.Add(Format('2^%d-1 %14.0n',[N,Mn+0.0]));
end;
end;
</syntaxhighlight>
{{out}}
<pre>
2^N-1 Prime
--------------------
2^2-1 3
2^3-1 7
2^5-1 31
2^7-1 127
2^13-1 8,191
2^17-1 131,071
2^19-1 524,287
2^31-1 2,147,483,647
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
if num mod 2 = 0
if num = 2
return 1
.
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
base = 4
for p = 2 to 52
if isprim (base - 1) = 1
print "2 ^ " & p & " - 1"
.
base *= 2
.
</syntaxhighlight>
{{out}}
<pre>
2 ^ 2 - 1
2 ^ 3 - 1
2 ^ 5 - 1
2 ^ 7 - 1
2 ^ 13 - 1
2 ^ 17 - 1
2 ^ 19 - 1
2 ^ 31 - 1
</pre>
=={{header|F_Sharp|F#}}==
{{trans|C#}}
<
open System.Numerics
Line 385 ⟶ 826:
loop 2 0 |> ignore
0 // return an integer exit code</
{{out}}
<pre>2 ^ 2 - 1
Line 399 ⟶ 840:
=={{header|Factor}}==
Factor comes with a Lucas-Lehmer primality test.
<
: mersennes-upto ( n -- seq ) [1,b] [ lucas-lehmer ] filter ;
3500 mersennes-upto [ "2 ^ %d - 1\n" printf ] each</
{{out}}
<pre>
Line 428 ⟶ 869:
=={{header|Fortran}}==
{{Trans|C}}
<
program mersenne
use iso_fortran_env, only: output_unit, INT64
Line 476 ⟶ 917:
end function is_prime
end program mersenne
</syntaxhighlight>
{{out}}
Line 488 ⟶ 929:
2^ 19 - 1
2^ 31 - 1
</pre>
=={{header|Frink}}==
Frink has built-in routines for iterating through prime numbers. Frink's <CODE>isPrime[n]</CODE> function automatically detects numbers of the form 2<sup>n</sup>-1 and performs a more efficient Lucas-Lehmer primality test on the number. This works with arbitrarily large numbers.
Did you know that all Java-based JVM languages are many many orders of magnitude faster because Frink's developer contributed vastly faster BigInteger algorithms to Java? It took the Java developers 11 years to integrate them but they became part of 1.8 and later! Operations that used to take days now can be done in seconds thanks to Frink's contributions to Java.
<syntaxhighlight lang="frink">for n = primes[]
if isPrime[2^n - 1]
println["2^$n - 1"]</syntaxhighlight>
{{out}}
<pre>
2^2 - 1
2^3 - 1
2^5 - 1
2^7 - 1
2^13 - 1
2^17 - 1
2^19 - 1
2^31 - 1
2^61 - 1
2^89 - 1
2^107 - 1
2^127 - 1
2^521 - 1
2^607 - 1
2^1279 - 1
2^2203 - 1
2^2281 - 1
2^3217 - 1
2^4253 - 1
2^4423 - 1
2^9689 - 1
2^9941 - 1
2^11213 - 1
2^19937 - 1
2^21701 - 1
...
</pre>
Line 499 ⟶ 977:
Note that the use of ProbablyPrime(0) requires Go 1.8 or later. When using the <code>math/big</code> package, passing a parameter of zero to this method forces it to apply only the Baillie-PSW test to check for primality. This is 100% accurate for numbers up to 2^64 and at the time of writing (June 2018) no known composite number above that bound passes the test.
<
import (
Line 540 ⟶ 1,018:
}
}
}</
{{out|text=using the GMP package on a 3.4 GHz Xeon E3-1245:}}
Line 570 ⟶ 1,048:
This can be sped up quite a bit for modern multi-core CPUs by some simple changes to use goroutines.
<
import (
Line 635 ⟶ 1,113:
}
}
}</
<!-- The output and the previous should be done on the same hardware to keep the numbers comparible; if changing/updating one change the other too. -->
{{out|text=using the GMP package on the same 3.4 GHz Xeon E3-1245 (4 core × 2 SMT threads) as above:}}
Line 666 ⟶ 1,144:
Using this approach, the Celeron machine (dual core) takes ~180 seconds to reach M<sub>9941</sub> and ~270 seconds to reach M<sub>11213</sub>.
=={{header|Haskell}}==
<
import Text.Printf (printf)
Line 677 ⟶ 1,155:
main = mapM_ (printf "M %d\n") $ take 20 mersenne
where
mersenne = filter lucasLehmer primes</
{{out}}
<pre>
Line 701 ⟶ 1,179:
M 9689
</pre>
=={{header|J}}==
<syntaxhighlight lang="j"> I. 1 p: <: 2x ^ i. 1280
2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<
public class MersennePrimes {
Line 741 ⟶ 1,223:
}
}
}</
{{out}}
<pre>2 ^ 2 - 1
Line 769 ⟶ 1,251:
Julia module <code>Primes</code> uses Miller-Rabin primality test.
<
mersenne(n::Integer) = convert(typeof(n), 2) ^ n - one(n)
Line 783 ⟶ 1,265:
end
main(big(20))</
{{out}}
Line 812 ⟶ 1,294:
A 'certainty' parameter of 10 is enough to find the first 20 Mersenne primes but as even this takes about 90 seconds on my modest machine I've not bothered going beyond that.
<
import java.math.BigInteger
Line 851 ⟶ 1,333:
}
}
}</
{{out}}
Line 879 ⟶ 1,361:
=={{header|Lua}}==
This checks for primality using a trial division function. The limitation is 'until p == p + 1', meaning that the program will halt when Lua's number type (a 64-bit floating point value) no longer has enough precision to distiguish between one integer and the next.
<
function isPrime (x)
if x < 2 then return false end
Line 898 ⟶ 1,380:
print("2 ^ " .. i .. " - 1 = " .. p)
end
until p == p + 1</
{{out}}
<pre>2 ^ 2 - 1 = 3
Line 909 ⟶ 1,391:
2 ^ 31 - 1 = 2147483647</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Mathematica has a built-in function to show the Mersenne primes:
<syntaxhighlight lang="mathematica">MersennePrimeExponent /@ Range[40]</syntaxhighlight>
{{out}}
<pre>{2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011}</pre>
Alternatively, we can calculate them:
<syntaxhighlight lang="mathematica">res = {};
Do[
If[PrimeQ[2^i - 1],
AppendTo[res, i];
If[Length[res] == 20,
Break[]
]
]
,
{i, 1, \[Infinity]}
]
res</syntaxhighlight>
{{out}}
<pre>{2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423}</pre>
=={{header|Nim}}==
===Using only standard library===
If we want to use only the standard library, we are limited to 64 bits. So we used a simple primality test.
<
if n == 1: return false
if n mod 3 == 0: return n == 3
Line 928 ⟶ 1,431:
if isOddPrime(p - 1):
echo "2^", e, " - 1"
p *= 2</
{{out}}
Line 944 ⟶ 1,447:
{{libheader|bignum}}
The module <code>bignum</code> provides big integers and a probabilistic primality test. We searched the Mersenne numbers for exponents between 1 and 10_000.
<
var p = newInt(2)
Line 950 ⟶ 1,453:
if probablyPrime(p - 1, 25) != 0:
echo "2^", e, " - 1"
p *= 2</
{{out}}
Line 977 ⟶ 1,480:
=={{header|PARI/GP}}==
<
my(m=Mod(4,1<<p-1));
for(i=3,p,m=m^2-2);
m==0
};
forprime(p=2,, if(LL(p), print("2^"p"-1")))</
=={{header|Perl}}==
Line 990 ⟶ 1,493:
{{libheader|ntheory}}
<
forprimes { is_mersenne_prime($_) && say } 1e9;</
{{out}}
<pre>
Line 1,008 ⟶ 1,511:
=={{header|Phix}}==
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">mp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">bp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">14</span><span style="color: #0000FF;">:</span><span style="color: #000000;">17</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"2^%d-1%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span><span style="color: #0000FF;">?</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">:</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bp</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bp</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">({</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bp</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,054 ⟶ 1,559:
=={{header|PHP}}==
<
function is_prime($n) {
Line 1,082 ⟶ 1,587:
echo '2 ^ ', $i, ' - 1', PHP_EOL;
}
}</
{{out}}
Line 1,094 ⟶ 1,599:
2 ^ 31 - 1
2 ^ 61 - 1</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
(de isprime (N)
(cache '(NIL) N
(if (== N 2)
T
(and
(> N 1)
(bit? 1 N)
(let (Q (dec N) N1 (dec N) K 0 X)
(until (bit? 1 Q)
(setq
Q (>> 1 Q)
K (inc K) ) )
(catch 'composite
(do 16
(loop
(setq X
(**Mod
(rand 2 (min (dec N) 1000000000000))
Q
N ) )
(T (or (=1 X) (= X N1)))
(T
(do K
(setq X (**Mod X 2 N))
(when (=1 X) (throw 'composite))
(T (= X N1) T) ) )
(throw 'composite) ) )
(throw 'composite T) ) ) ) ) ) )
(for N 1000
(and
(isprime (dec (** 2 N)))
(prinl "2 \^ " N " - 1") ) )</syntaxhighlight>
{{out}}
<pre>
2 ^ 2 - 1
2 ^ 3 - 1
2 ^ 5 - 1
2 ^ 7 - 1
2 ^ 13 - 1
2 ^ 17 - 1
2 ^ 19 - 1
2 ^ 31 - 1
2 ^ 61 - 1
2 ^ 89 - 1
2 ^ 107 - 1
2 ^ 127 - 1
2 ^ 521 - 1
2 ^ 607 - 1
</pre>
=={{header|Pike}}==
<
while(power++) {
int candidate = 2->pow(power)-1;
if( candidate->probably_prime_p() )
write("2 ^ %d - 1\n", power);
}</
Output:
<pre>
Line 1,117 ⟶ 1,681:
=={{header|Prolog}}==
Lucas-Lehmer test, works with SWI Prolog
<
lucas_lehmer_seq(M, L) :-
lazy_list(ll_iter, 4-M, L).
Line 1,134 ⟶ 1,698:
Skip is P - 3, drop(Skip, Residues, [R|_]),
R =:= 0.
</syntaxhighlight>
{{out}}
<pre>
Line 1,144 ⟶ 1,708:
=={{header|Python}}==
{{trans|Java}}
<
#Take from https://www.codeproject.com/Articles/691200/%2FArticles%2F691200%2FPrimality-test-algorithms-Prime-test-The-fastest-w
Line 1,227 ⟶ 1,791:
if MillerRabinPrimalityTest(p):
break
print "done"</
{{out}}
<pre>2 ^ 2 - 1
Line 1,262 ⟶ 1,826:
It doesn't specify to ''calculate'' them, only to ''list'' them; why throw away all of the computer '''millenia''' of processing power that the GIMPS has invested?
<syntaxhighlight lang="raku"
use Gumbo;
Line 1,272 ⟶ 1,836:
for $table[1]».[*][0][*].comb(/'exp_lo='\d+/)».subst(/\D/, '',:g)
.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]).words;
</syntaxhighlight>
{{out}}
<pre>All known Mersenne primes as of 2018-12-21
Line 1,330 ⟶ 1,894:
This REXX version (using a 32-bit Regina REXX interpreter) will find those Mersenne primes which are less than
<br>8 million decimal digits (which would be '''M43''').
<
do j=1; /*process a range, or run out of time.*/
if \isPrime(j) then iterate /*if J isn't a prime, keep plugging.*/
Line 1,370 ⟶ 1,934:
end /*until*/
if sq==1 then return q /*Not a prime? Return a factor.*/
end /*k*/</
<br><br>
=={{header|Ring}}==
<
# Project : Mersenne primes
Line 1,392 ⟶ 1,956:
next
return 1
</syntaxhighlight>
Output:
<pre>
Line 1,403 ⟶ 1,967:
19
</pre>
=={{header|RPL}}==
This version use binary integers
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ / LAST ROT * - #0 == ≫ ''''BDIV?'''' STO
≪
'''IF''' DUP #3 ≤ '''THEN''' #2 / B→R
'''ELSE'''
'''IF''' DUP #2 '''BDIV?''' OVER #3 '''BDIV?''' OR
'''THEN''' DROP 0
'''ELSE'''
DUP B→R √ R→B → a maxd
≪ a #2 #5
'''WHILE''' a OVER '''BDIV?''' NOT OVER maxd ≤ AND
'''REPEAT''' OVER + #6 ROT - SWAP '''END'''
≫
SWAP DROP '''BDIV?''' NOT
'''END'''
'''END'''
≫ ''''BPRIM?'''' STO
≪ {} 1 32 '''FOR''' n
#1 1 n '''START''' SL '''NEXT''' #1 -
'''IF BPRIM? THEN''' + '''END'''
'''NEXT'''
≫ EVAL
|
''( #a #b -- boolean )''
''( #a -- boolean )''
return 1 if a is 2 or 3
if 2 or 3 divides a
return 0
else
store a and root(a)
initialize stack with a i d
while d does not divide a and d <= root(a)
i = 6 - i which modifies 2 into 4 and viceversa
convert stack status into result
Let's loop
Generate M(n)
test primality
|}
{{out}}
<pre>
{ 2 3 5 7 13 17 19 31 }
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'openssl'
(0..).each{|n| puts "2**#{n} - 1" if OpenSSL::BN.new(2**n -1).prime? }
</syntaxhighlight>
{{out}}
<pre>2**2 - 1
2**3 - 1
2**5 - 1
2**7 - 1
2**13 - 1
2**17 - 1
2**19 - 1
2**31 - 1
2**61 - 1
2**89 - 1
2**107 - 1
2**127 - 1
2**521 - 1
2**607 - 1
2**1279 - 1
2**2203 - 1
2**2281 - 1
2**3217 - 1
2**4253 - 1
^Ctest2.rb:7:in `prime?': Interrupt
</pre>
=={{header|Scala}}==
<syntaxhighlight lang="scala">
object MersennePrimes extends App {
Line 1,433 ⟶ 2,087:
println("That's All Folks!")
}
</syntaxhighlight>
=={{header|Sidef}}==
Uses the ''is_mersenne_prime()'' function from [https://metacpan.org/pod/Math::Prime::Util::GMP Math::Prime::Util::GMP].
<
say "2^#{p} - 1"
}</
{{out}}
<pre>
Line 1,466 ⟶ 2,120:
^C
sidef mersenne.sf 12.47s user 0.02s system 99% cpu 12.495 total
</pre>
=={{header|Transd}}==
<syntaxhighlight lang="Scheme">#lang transd
MainModule: {
_start: (λ locals: curexp 1 maxexp 1000 base BigLong(2)
(while (< curexp maxexp)
(+= curexp 1)
(if (not (is-prime BigLong(curexp))) continue)
(with cand (- (pow base curexp) 1)
(if (is-probable-prime cand 10)
(lout curexp " : " cand ))
) ) )
}</syntaxhighlight>
{{out}}
<pre>
2 : 3
3 : 7
5 : 31
7 : 127
13 : 8191
17 : 131071
19 : 524287
31 : 2147483647
61 : 2305843009213693951
89 : 618970019642690137449562111
107 : 162259276829213363391578010288127
127 : 170141183460469231731687303715884105727
521 : 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607 : 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 1,554 ⟶ 2,240:
End Sub
End Module</
{{out}}
<pre>2 ^ 2 - 1
Line 1,567 ⟶ 2,253:
=={{header|Wren}}==
===Wren-CLI===
{{libheader|Wren-math}}
{{libheader|Wren-big}}
A bit slow so limited to first 14 Mersenne primes.
<
import "./big" for BigInt
var MAX = 14
Line 1,588 ⟶ 2,275:
if (Int.isPrime(p)) break
}
}</
{{out}}
Line 1,607 ⟶ 2,294:
2 ^ 521 - 1
2 ^ 607 - 1
</pre>
===Embedded (GMP)===
{{libheader|Wren-gmp}}
This finds the first 23 Mersenne primes in about 172 seconds which is virtually the same as the Go non-concurrent version using their GMP plug-in when run on my machine.
<syntaxhighlight lang="wren">import "./math" for Int
import "./gmp" for Mpz
var MAX = 23
System.print("The first %(MAX) Mersenne primes are:")
var count = 0
var p = 2
while (true) {
var m = Mpz.one.lsh(p).sub(1)
if (m.probPrime(15) > 0) {
System.print("2 ^ %(p) - 1")
count = count + 1
if (count == MAX) break
}
while (true) {
p = (p > 2) ? p + 2 : 3
if (Int.isPrime(p)) break
}
}</syntaxhighlight>
{{out}}
<pre>
The first 23 Mersenne primes are:
2 ^ 2 - 1
2 ^ 3 - 1
2 ^ 5 - 1
2 ^ 7 - 1
2 ^ 13 - 1
2 ^ 17 - 1
2 ^ 19 - 1
2 ^ 31 - 1
2 ^ 61 - 1
2 ^ 89 - 1
2 ^ 107 - 1
2 ^ 127 - 1
2 ^ 521 - 1
2 ^ 607 - 1
2 ^ 1279 - 1
2 ^ 2203 - 1
2 ^ 2281 - 1
2 ^ 3217 - 1
2 ^ 4253 - 1
2 ^ 4423 - 1
2 ^ 9689 - 1
2 ^ 9941 - 1
2 ^ 11213 - 1
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
int N;
[for N:= 1 to 31 do
if IsPrime(1<<N-1) then
[Text(0, "2^^"); IntOut(0, N); Text(0, " - 1");
CrLf(0);
];
]</syntaxhighlight>
{{out}}
<pre>
2^2 - 1
2^3 - 1
2^5 - 1
2^7 - 1
2^13 - 1
2^17 - 1
2^19 - 1
2^31 - 1
</pre>
Line 1,612 ⟶ 2,381:
{{libheader|GMP}}
Uses libGMP (GNU MP Bignum Library) and its Miller-Rabin probabilistic primality testing algorithm.
<
fcn mprimes{
n,m := BN(2),0;
Line 1,620 ⟶ 2,389:
}
}()
// gets rather slow after M(4423)</
{{out}}
<pre style="height:40ex">
| |||