Mersenne primes: Difference between revisions
m
Fixed minor typo
m (Fixed minor typo) |
|||
| (18 intermediate revisions by 10 users not shown) | |||
Line 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="
on isPrime(integ)
set isComposite to ""
Line 92 ⟶ 239:
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}}==
Line 132 ⟶ 347:
2 ^ 61 - 1
</pre>
=={{header|BASIC}}==
Line 251 ⟶ 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++}}==
Line 406 ⟶ 673:
2 ^ 19 - 1
2 ^ 31 - 1</pre>
=={{header|Delphi}}==
{{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#}}==
Line 815 ⟶ 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}}==
Line 1,599 ⟶ 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}}==
Line 1,795 ⟶ 2,253:
=={{header|Wren}}==
===Wren-CLI===
{{libheader|Wren-math}}
{{libheader|Wren-big}}
A bit slow so limited to first 14 Mersenne primes.
<syntaxhighlight lang="
import "./big" for BigInt
var MAX = 14
Line 1,835 ⟶ 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>
| |||