Mersenne primes: Difference between revisions
m
Fixed minor typo
m (Fixed minor typo) |
|||
| (13 intermediate revisions by 9 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>
Line 101 ⟶ 202:
=={{header|AppleScript}}==
<syntaxhighlight lang="
on isPrime(integ)
set isComposite to ""
Line 138 ⟶ 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 178 ⟶ 347:
2 ^ 61 - 1
</pre>
=={{header|BASIC}}==
Line 297 ⟶ 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 452 ⟶ 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 861 ⟶ 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,706 ⟶ 2,028:
{ 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,902 ⟶ 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,942 ⟶ 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>
| |||