Mersenne primes: Difference between revisions
m
Fixed minor typo
No edit summary |
m (Fixed minor typo) |
||
| (9 intermediate revisions by 5 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 364 ⟶ 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 577 ⟶ 731:
</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 986 ⟶ 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,858 ⟶ 2,055:
^Ctest2.rb:7:in `prime?': Interrupt
</pre>
=={{header|Scala}}==
Line 2,054 ⟶ 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 2,094 ⟶ 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>
| |||