Lucas-Lehmer test: Difference between revisions
Content added Content deleted
(Changed the recent entry by one which is ready to run and can handle much more digits) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 16: | Line 16: | ||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="11l">F isPrime(p) |
||
I p < 2 | p % 2 == 0 |
I p < 2 | p % 2 == 0 |
||
R p == 2 |
R p == 2 |
||
Line 37: | Line 37: | ||
L(p) 2..2299 |
L(p) 2..2299 |
||
I isMersennePrime(p) |
I isMersennePrime(p) |
||
print(‘M’p, end' ‘ ’)</ |
print(‘M’p, end' ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 46: | Line 46: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
For maximum compatibility, this program uses only the basic instruction set. |
For maximum compatibility, this program uses only the basic instruction set. |
||
< |
<syntaxhighlight lang="360asm">* Lucas-Lehmer test |
||
LUCASLEH CSECT |
LUCASLEH CSECT |
||
USING LUCASLEH,R12 |
USING LUCASLEH,R12 |
||
Line 118: | Line 118: | ||
LTORG |
LTORG |
||
YREGS |
YREGS |
||
END LUCASLEH</ |
END LUCASLEH</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>M002 |
<pre>M002 |
||
Line 130: | Line 130: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_Io; use Ada.Text_Io; |
||
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; |
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; |
||
Line 157: | Line 157: | ||
end if; |
end if; |
||
end loop; |
end loop; |
||
end Lucas_Lehmer_Test;</ |
end Lucas_Lehmer_Test;</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Mersenne primes: |
Mersenne primes: |
||
Line 165: | Line 165: | ||
Because of the very large numbers computed, |
Because of the very large numbers computed, |
||
the mapm binding is used to calculate with arbitrary precision. |
the mapm binding is used to calculate with arbitrary precision. |
||
< |
<syntaxhighlight lang="agena">readlib 'mapm'; |
||
mapm.xdigits(100); |
mapm.xdigits(100); |
||
Line 187: | Line 187: | ||
write('M' & i & ' ') |
write('M' & i & ' ') |
||
fi |
fi |
||
od;</ |
od;</syntaxhighlight> |
||
produces: |
produces: |
||
< |
<syntaxhighlight lang="agena">M3 M5 M7 M13 M17 M19 M31</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 195: | Line 195: | ||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''}} |
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''}} |
||
< |
<syntaxhighlight lang="algol68">PRAGMAT stack=1M precision=20000 PRAGMAT |
||
PROC is prime = ( INT p )BOOL: |
PROC is prime = ( INT p )BOOL: |
||
Line 233: | Line 233: | ||
count <= upb count |
count <= upb count |
||
DO SKIP OD |
DO SKIP OD |
||
)</ |
)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 243: | Line 243: | ||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
<syntaxhighlight lang="arm assembly"> |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
/* program lucaslehmer.s */ |
/* program lucaslehmer.s */ |
||
Line 459: | Line 459: | ||
iMagicNumber: .int 0xCCCCCCCD |
iMagicNumber: .int 0xCCCCCCCD |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 486: | Line 486: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">mersenne?: function [p][ |
||
if p=2 -> return true |
if p=2 -> return true |
||
mp: dec shl 1 p |
mp: dec shl 1 p |
||
Line 497: | Line 497: | ||
print "Mersenne primes:" |
print "Mersenne primes:" |
||
mersennes: select 2..32 'x -> and? prime? x mersenne? x |
mersennes: select 2..32 'x -> and? prime? x mersenne? x |
||
print join.with:", " map mersennes 'm -> ~"M|m|"</ |
print join.with:", " map mersennes 'm -> ~"M|m|"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 505: | Line 505: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f LUCAS-LEHMER_TEST.AWK |
# syntax: GAWK -f LUCAS-LEHMER_TEST.AWK |
||
# converted from Pascal |
# converted from Pascal |
||
Line 524: | Line 524: | ||
exit(0) |
exit(0) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 533: | Line 533: | ||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
Using its native arithmetic BBC BASIC can only test up to M23. |
Using its native arithmetic BBC BASIC can only test up to M23. |
||
< |
<syntaxhighlight lang="bbcbasic"> *FLOAT 64 |
||
PRINT "Mersenne Primes:" |
PRINT "Mersenne Primes:" |
||
FOR p% = 2 TO 23 |
FOR p% = 2 TO 23 |
||
Line 550: | Line 550: | ||
sn -= (mp * INT(sn / mp)) |
sn -= (mp * INT(sn / mp)) |
||
NEXT |
NEXT |
||
= (sn = 0)</ |
= (sn = 0)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 566: | Line 566: | ||
{{trans|Zig}} |
{{trans|Zig}} |
||
Uses the 64 bit version |
Uses the 64 bit version |
||
<syntaxhighlight lang="bcpl"> |
|||
<lang BCPL> |
|||
GET "libhdr" |
GET "libhdr" |
||
Line 595: | Line 595: | ||
RESULTIS 0 |
RESULTIS 0 |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 612: | Line 612: | ||
If a number cannot be factorized, (either because it is prime or because it is to great to fit in a computer word) the root expression doesn't change much. |
If a number cannot be factorized, (either because it is prime or because it is to great to fit in a computer word) the root expression doesn't change much. |
||
For example, the expression <code>13^(13^-1)</code> becomes <code>13^1/13</code>, and this matches the pattern <code>13^%</code>. |
For example, the expression <code>13^(13^-1)</code> becomes <code>13^1/13</code>, and this matches the pattern <code>13^%</code>. |
||
< |
<syntaxhighlight lang="bracmat"> ( clk$:?t0:?now |
||
& ( time |
& ( time |
||
= ( print |
= ( print |
||
Line 657: | Line 657: | ||
) |
) |
||
& done |
& done |
||
);</ |
);</syntaxhighlight> |
||
{{Out}} (after 4.5 hours): |
{{Out}} (after 4.5 hours): |
||
<pre>0,00 0,00 s: M3 is PRIME! |
<pre>0,00 0,00 s: M3 is PRIME! |
||
Line 685: | Line 685: | ||
=={{header|Burlesque}}== |
=={{header|Burlesque}}== |
||
< |
<syntaxhighlight lang="burlesque">607rz2en{J4{J.*2.-2{th}c!**-..%}#R2.-E!n!it}f[2+]{2\/**-.}m[p^</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 713: | Line 713: | ||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <limits.h> |
#include <limits.h> |
||
Line 788: | Line 788: | ||
printf("\n"); |
printf("\n"); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 798: | Line 798: | ||
{{works with|C99}} |
{{works with|C99}} |
||
Compiler options: gcc -std=c99 -lm Lucas-Lehmer_test.c -o Lucas-Lehmer_test<br> |
Compiler options: gcc -std=c99 -lm Lucas-Lehmer_test.c -o Lucas-Lehmer_test<br> |
||
< |
<syntaxhighlight lang="c">#include <math.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <limits.h> |
#include <limits.h> |
||
Line 842: | Line 842: | ||
} |
} |
||
printf("\n"); |
printf("\n"); |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 853: | Line 853: | ||
{{works with|Visual Studio|2010}} |
{{works with|Visual Studio|2010}} |
||
{{works with|.NET Framework|4.0}} |
{{works with|.NET Framework|4.0}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Numerics; |
using System.Numerics; |
||
Line 899: | Line 899: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} (Run only to 11213) |
{{out}} (Run only to 11213) |
||
Line 909: | Line 909: | ||
The mod function, (<code>%</code>) has a computation cost equivalent to the divide operation. In this case, a combination of ands, shifts and adds can replace the mod function. Another change is creating the list of candidate Mersenne numbers in descending order, the point being to start the more time consuming calculations first. This avoids a long calculation occurring by itself at the end of the <code>Parallel.For</code> queue. Also added trial division step, translated from the '''Rust''' and '''C''' versions. |
The mod function, (<code>%</code>) has a computation cost equivalent to the divide operation. In this case, a combination of ands, shifts and adds can replace the mod function. Another change is creating the list of candidate Mersenne numbers in descending order, the point being to start the more time consuming calculations first. This avoids a long calculation occurring by itself at the end of the <code>Parallel.For</code> queue. Also added trial division step, translated from the '''Rust''' and '''C''' versions. |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Numerics; |
using System.Numerics; |
||
Line 945: | Line 945: | ||
if (System.Diagnostics.Debugger.IsAttached) Console.ReadLine(); |
if (System.Diagnostics.Debugger.IsAttached) Console.ReadLine(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 |
<pre>M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 |
||
Line 955: | Line 955: | ||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <gmpxx.h> |
#include <gmpxx.h> |
||
Line 991: | Line 991: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} (Incomplete; It takes a long time.) |
{{out}} (Incomplete; It takes a long time.) |
||
Line 999: | Line 999: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="lisp">(defn prime? [i] |
||
(cond (< i 4) (>= i 2) |
(cond (< i 4) (>= i 2) |
||
(zero? (rem i 2)) false |
(zero? (rem i 2)) false |
||
Line 1,011: | Line 1,011: | ||
(recur (inc n) (rem (- (* s s) 2) mp))))))) |
(recur (inc n) (rem (- (* s s) 2) mp))))))) |
||
(filter mersenne? (filter prime? (iterate inc 1)))</ |
(filter mersenne? (filter prime? (iterate inc 1)))</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,020: | Line 1,020: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
Coffee Script is really hampered by its lack of full syntactic support for JavaScript generators. The loop to collect Mersenne numbers must be done in imperative style, rather than a more functional style, when using the infinite lazy prime generator. |
Coffee Script is really hampered by its lack of full syntactic support for JavaScript generators. The loop to collect Mersenne numbers must be done in imperative style, rather than a more functional style, when using the infinite lazy prime generator. |
||
<syntaxhighlight lang="coffeescript"> |
|||
<lang CoffeeScript> |
|||
sorenson = require('sieve').primes # Sorenson's extensible sieve from task: Extensible Prime Number Generator |
sorenson = require('sieve').primes # Sorenson's extensible sieve from task: Extensible Prime Number Generator |
||
Line 1,041: | Line 1,041: | ||
console.log "Some Mersenne primes: #{"M" + String p for p in mersennes}" |
console.log "Some Mersenne primes: #{"M" + String p for p in mersennes}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,050: | Line 1,050: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
{{trans|Clojure}} |
{{trans|Clojure}} |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun or-f (&optional a b) (or a b));necessary for reduce, as 'or' is implemented as a macro |
(defun or-f (&optional a b) (or a b));necessary for reduce, as 'or' is implemented as a macro |
||
Line 1,067: | Line 1,067: | ||
(princ (remove-if-not #'mersenne-p (remove-if-not #'prime-p (loop for i to 5000 collect i)))) |
(princ (remove-if-not #'mersenne-p (remove-if-not #'prime-p (loop for i to 5000 collect i)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,075: | Line 1,075: | ||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="ruby">require "big" |
||
def is_prime(n) # P3 Prime Generator primality test |
def is_prime(n) # P3 Prime Generator primality test |
||
Line 1,110: | Line 1,110: | ||
break if count >= upb_count |
break if count >= upb_count |
||
end |
end |
||
puts</ |
puts</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,118: | Line 1,118: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.math, std.bigint; |
||
bool isPrime(in uint p) pure nothrow @safe @nogc { |
bool isPrime(in uint p) pure nothrow @safe @nogc { |
||
Line 1,147: | Line 1,147: | ||
stdout.flush; |
stdout.flush; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 </pre> |
<pre>M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 </pre> |
||
Line 1,155: | Line 1,155: | ||
=={{header|DWScript}}== |
=={{header|DWScript}}== |
||
Using Integer type, which is 64bit, limits the search to M31. |
Using Integer type, which is 64bit, limits the search to M31. |
||
< |
<syntaxhighlight lang="delphi">function IsMersennePrime(p : Integer) : Boolean; |
||
var |
var |
||
i, s, m_p : Integer; |
i, s, m_p : Integer; |
||
Line 1,180: | Line 1,180: | ||
Print(' M'+IntToStr(p)); |
Print(' M'+IntToStr(p)); |
||
end; |
end; |
||
PrintLn('');</ |
PrintLn('');</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> M2 M3 M5 M7 M13 M17 M19 M31</pre> |
<pre> M2 M3 M5 M7 M13 M17 M19 M31</pre> |
||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(require 'bigint) |
(require 'bigint) |
||
(define (mersenne-prime? odd-prime: p) |
(define (mersenne-prime? odd-prime: p) |
||
Line 1,205: | Line 1,205: | ||
→ M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 |
→ M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang="elixir">defmodule LucasLehmer do |
||
use Bitwise |
use Bitwise |
||
def test do |
def test do |
||
Line 1,222: | Line 1,222: | ||
end |
end |
||
LucasLehmer.test</ |
LucasLehmer.test</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,230: | Line 1,230: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang">-module(mp). |
||
-export([main/0]). |
-export([main/0]). |
||
Line 1,236: | Line 1,236: | ||
s(MP,1) -> 4 rem MP; |
s(MP,1) -> 4 rem MP; |
||
s(MP,N) -> X=s(MP,N-1), (X*X - 2) rem MP.</ |
s(MP,N) -> X=s(MP,N-1), (X*X - 2) rem MP.</syntaxhighlight> |
||
In 3 seconds will print |
In 3 seconds will print |
||
Line 1,246: | Line 1,246: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
With native arithmetic up to 23: for bigger numbers you must use MULPREC program. |
With native arithmetic up to 23: for bigger numbers you must use MULPREC program. |
||
< |
<syntaxhighlight lang="erre">PROGRAM LL_TEST |
||
!$DOUBLE |
!$DOUBLE |
||
Line 1,270: | Line 1,270: | ||
END FOR |
END FOR |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Mersenne Primes: |
<pre>Mersenne Primes: |
||
Line 1,284: | Line 1,284: | ||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||
Simple arbitrary-precision version: |
Simple arbitrary-precision version: |
||
< |
<syntaxhighlight lang="fsharp">let rec s mp n = |
||
if n = 1 then 4I % mp else ((s mp (n - 1)) ** 2 - 2I) % mp |
if n = 1 then 4I % mp else ((s mp (n - 1)) ** 2 - 2I) % mp |
||
[ for p in 2..47 do |
[ for p in 2..47 do |
||
if p = 2 || s ((1I <<< p) - 1I) (p - 1) = 0I then |
if p = 2 || s ((1I <<< p) - 1I) (p - 1) = 0I then |
||
yield p ]</ |
yield p ]</syntaxhighlight> |
||
Tail-recursive version: |
Tail-recursive version: |
||
< |
<syntaxhighlight lang="fsharp">let IsMersennePrime exponent = |
||
if exponent <= 1 then failwith "Exponent must be >= 2" |
if exponent <= 1 then failwith "Exponent must be >= 2" |
||
let prime = 2I ** exponent - 1I; |
let prime = 2I ** exponent - 1I; |
||
Line 1,302: | Line 1,302: | ||
LucasLehmer 0 4I = 0I |
LucasLehmer 0 4I = 0I |
||
</syntaxhighlight> |
|||
</lang> |
|||
Version using library folding function (way shorter and faster than the above): |
Version using library folding function (way shorter and faster than the above): |
||
< |
<syntaxhighlight lang="fsharp">let IsMersennePrime exponent = |
||
if exponent <= 1 then failwith "Exponent must be >= 2" |
if exponent <= 1 then failwith "Exponent must be >= 2" |
||
let prime = 2I ** exponent - 1I; |
let prime = 2I ** exponent - 1I; |
||
Line 1,313: | Line 1,313: | ||
LucasLehmer = 0I |
LucasLehmer = 0I |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: io math.primes.lucas-lehmer math.ranges prettyprint |
||
sequences ; |
sequences ; |
||
47 [1,b] [ lucas-lehmer ] filter |
47 [1,b] [ lucas-lehmer ] filter |
||
"Mersenne primes:" print |
"Mersenne primes:" print |
||
[ "M" write pprint bl ] each nl</ |
[ "M" write pprint bl ] each nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,329: | Line 1,329: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
<lang>: lucas-lehmer |
<syntaxhighlight lang="text">: lucas-lehmer |
||
1+ 2 do |
1+ 2 do |
||
4 i 2 <> * abs swap 1+ dup + 1- swap |
4 i 2 <> * abs swap 1+ dup + 1- swap |
||
Line 1,336: | Line 1,336: | ||
; |
; |
||
1 15 lucas-lehmer</ |
1 15 lucas-lehmer</syntaxhighlight> |
||
==Alternate version to handle 64 and 128 bit integers.== |
==Alternate version to handle 64 and 128 bit integers.== |
||
Forth supports modular multiplication without overflow by having mixed mode operations that work on 128 bit intermediate results. It's also possible to do do the Lucas-Lehmer test using double-precision (128 bit) integers, though support for that is more limited in the Forth language, so requires writing more support code. This version contains the code for both 64 bit (mixed mode) and 128 bit (double precision mode) |
Forth supports modular multiplication without overflow by having mixed mode operations that work on 128 bit intermediate results. It's also possible to do do the Lucas-Lehmer test using double-precision (128 bit) integers, though support for that is more limited in the Forth language, so requires writing more support code. This version contains the code for both 64 bit (mixed mode) and 128 bit (double precision mode) |
||
<syntaxhighlight lang="forth"> |
|||
<lang Forth> |
|||
18 constant π-64 \ count of primes < 64 |
18 constant π-64 \ count of primes < 64 |
||
31 constant π-128 \ count of primes < 128 |
31 constant π-128 \ count of primes < 128 |
||
Line 1,407: | Line 1,407: | ||
if 'M emit i c@ . then |
if 'M emit i c@ . then |
||
loop ; |
loop ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,421: | Line 1,421: | ||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
Only Mersenne number with prime exponent can be themselves prime but for the small numbers used in this example it was not worth the effort to include this check. As the size of the exponent increases this becomes more important. |
Only Mersenne number with prime exponent can be themselves prime but for the small numbers used in this example it was not worth the effort to include this check. As the size of the exponent increases this becomes more important. |
||
< |
<syntaxhighlight lang="fortran">PROGRAM LUCAS_LEHMER |
||
IMPLICIT NONE |
IMPLICIT NONE |
||
Line 1,441: | Line 1,441: | ||
END DO |
END DO |
||
END PROGRAM LUCAS_LEHMER</ |
END PROGRAM LUCAS_LEHMER</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
===Native types for Mersenne primes <= M63=== |
===Native types for Mersenne primes <= M63=== |
||
< |
<syntaxhighlight lang="freebasic">' version 18-09-2015 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,497: | Line 1,497: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> M3 M5 M7 M13 M17 M19 M31 M61</pre> |
<pre> M3 M5 M7 M13 M17 M19 M31 M61</pre> |
||
==={{libheader|GMP}}=== |
==={{libheader|GMP}}=== |
||
Uses the trick from the '''C''' entry to avoid the slow Mod |
Uses the trick from the '''C''' entry to avoid the slow Mod |
||
< |
<syntaxhighlight lang="freebasic">' version 18-09-2015 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,583: | Line 1,583: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>M3 M5 M7 M13 M17 |
<pre>M3 M5 M7 M13 M17 |
||
Line 1,594: | Line 1,594: | ||
Frink's <CODE>isPrime</CODE> function automatically detects numbers of the form 2<sup>n</sup>-1 and performs a Lucas-Lehmer test on them, including testing if n is prime, which is sufficient to prove primality for this form. |
Frink's <CODE>isPrime</CODE> function automatically detects numbers of the form 2<sup>n</sup>-1 and performs a Lucas-Lehmer test on them, including testing if n is prime, which is sufficient to prove primality for this form. |
||
< |
<syntaxhighlight lang="frink"> |
||
for n = primes[] |
for n = primes[] |
||
if isPrime[2^n-1] |
if isPrime[2^n-1] |
||
println[n] |
println[n] |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|FunL}}== |
=={{header|FunL}}== |
||
< |
<syntaxhighlight lang="funl">def mersenne( p ) = |
||
if p == 2 then return true |
if p == 2 then return true |
||
Line 1,615: | Line 1,615: | ||
for p <- primes().filter( mersenne ).take( 20 ) |
for p <- primes().filter( mersenne ).take( 20 ) |
||
println( 'M' + p )</ |
println( 'M' + p )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,643: | Line 1,643: | ||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap">LucasLehmer := function(n) |
||
local i, m, s; |
local i, m, s; |
||
if n = 2 then |
if n = 2 then |
||
Line 1,660: | Line 1,660: | ||
Filtered([1 .. 2000], LucasLehmer); |
Filtered([1 .. 2000], LucasLehmer); |
||
[2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279]</ |
[2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279]</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
Processing the first list indicates that the test works. Processing the second shows it working on some larger numbers. |
Processing the first list indicates that the test works. Processing the second shows it working on some larger numbers. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,699: | Line 1,699: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,710: | Line 1,710: | ||
{{works with|GHC|6.8.2}} |
{{works with|GHC|6.8.2}} |
||
< |
<syntaxhighlight lang="haskell">module Main |
||
where |
where |
||
Line 1,721: | Line 1,721: | ||
lucasLehmer p = s (2^p-1) (p-1) == 0 |
lucasLehmer p = s (2^p-1) (p-1) == 0 |
||
printMersennes = mapM_ (\x -> putStrLn $ "M" ++ show x)</ |
printMersennes = mapM_ (\x -> putStrLn $ "M" ++ show x)</syntaxhighlight> |
||
It is pointed out on the [[Sieve of Eratosthenes]] page that the following "sieve" is inefficient. Nonetheless it takes very little time compared to the Lucas-Lehmer test itself. |
It is pointed out on the [[Sieve of Eratosthenes]] page that the following "sieve" is inefficient. Nonetheless it takes very little time compared to the Lucas-Lehmer test itself. |
||
< |
<syntaxhighlight lang="haskell">sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]</syntaxhighlight> |
||
It takes about 30 minutes to get up to: |
It takes about 30 minutes to get up to: |
||
<pre> |
<pre> |
||
Line 1,730: | Line 1,730: | ||
=={{header|HicEst}}== |
=={{header|HicEst}}== |
||
< |
<syntaxhighlight lang="hicest">s = 0 |
||
DO exponent = 2, 31 |
DO exponent = 2, 31 |
||
IF(exponent > 2) s = 4 |
IF(exponent > 2) s = 4 |
||
Line 1,740: | Line 1,740: | ||
ENDDO |
ENDDO |
||
END</ |
END</syntaxhighlight> |
||
=={{header|J}}== |
=={{header|J}}== |
||
Line 1,749: | Line 1,749: | ||
We use arbitrary-precision integers in order to be able to test any arbitrary prime. |
We use arbitrary-precision integers in order to be able to test any arbitrary prime. |
||
< |
<syntaxhighlight lang="java">import java.math.BigInteger; |
||
public class Mersenne |
public class Mersenne |
||
{ |
{ |
||
Line 1,793: | Line 1,793: | ||
System.out.println(); |
System.out.println(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} (after about eight hours): |
{{Out}} (after about eight hours): |
||
<pre> |
<pre> |
||
Line 1,803: | Line 1,803: | ||
In JavaScript we using BigInt ( numbers with 'n' suffix ) - so we can use really big numbers |
In JavaScript we using BigInt ( numbers with 'n' suffix ) - so we can use really big numbers |
||
<syntaxhighlight lang="javascript"> |
|||
<lang Javascript> |
|||
////////// In JavaScript we don't have sqrt for BigInt - so here is implementation |
////////// In JavaScript we don't have sqrt for BigInt - so here is implementation |
||
function newtonIteration(n, x0) { |
function newtonIteration(n, x0) { |
||
Line 1,863: | Line 1,863: | ||
} |
} |
||
console.log(`... Took: ${Date.now()-tm} ms`); |
console.log(`... Took: ${Date.now()-tm} ms`); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,902: | Line 1,902: | ||
Output includes the length of the decimal representation of the Mersenne prime. |
Output includes the length of the decimal representation of the Mersenne prime. |
||
< |
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic: |
||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
||
Line 1,934: | Line 1,934: | ||
| "M\($i):\($mp|tostring|length)" ); |
| "M\($i):\($mp|tostring|length)" ); |
||
mersenne_primes</ |
mersenne_primes</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,962: | Line 1,962: | ||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julia> |
|||
using Primes |
using Primes |
||
Line 1,979: | Line 1,979: | ||
getmersenneprimes(50) |
getmersenneprimes(50) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}}<pre> |
{{output}}<pre> |
||
M2, cumulative time elapsed: 0.019999980926513672 seconds |
M2, cumulative time elapsed: 0.019999980926513672 seconds |
||
Line 2,012: | Line 2,012: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
In view of the Java result, I've set the program to stop at M4423 so it will run in a reasonable time (about 85 seconds) on a typical laptop: |
In view of the Java result, I've set the program to stop at M4423 so it will run in a reasonable time (about 85 seconds) on a typical laptop: |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 2,058: | Line 2,058: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,070: | Line 2,070: | ||
With slight syntactic differences, this would also work with earlier versions of langur if you limit it to smaller numbers. 0.8 uses arbitrary precision. |
With slight syntactic differences, this would also work with earlier versions of langur if you limit it to smaller numbers. 0.8 uses arbitrary precision. |
||
< |
<syntaxhighlight lang="langur">val .isPrime = f .i == 2 or |
||
.i > 2 and not any f(.x) .i div .x, pseries 2 to .i ^/ 2 |
.i > 2 and not any f(.x) .i div .x, pseries 2 to .i ^/ 2 |
||
Line 2,083: | Line 2,083: | ||
} |
} |
||
writeln join " ", map f $"M\.x;", where .isMersennePrime, series 2300</ |
writeln join " ", map f $"M\.x;", where .isMersennePrime, series 2300</syntaxhighlight> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
This version is very speedy and is bounded. |
This version is very speedy and is bounded. |
||
< |
<syntaxhighlight lang="mathematica">Select[Table[M = 2^p - 1; |
||
For[i = 1; s = 4, i <= p - 2, i++, s = Mod[s^2 - 2, M]]; |
For[i = 1; s = 4, i <= p - 2, i++, s = Mod[s^2 - 2, M]]; |
||
If[s == 0, "M" <> ToString@p, p], {p, |
If[s == 0, "M" <> ToString@p, p], {p, |
||
Prime /@ Range[300]}], StringQ] |
Prime /@ Range[300]}], StringQ] |
||
=> {M3, M5, M7, M13, M17, M19, M31, M61, M89, M107, M127, M521, M607, M1279}</ |
=> {M3, M5, M7, M13, M17, M19, M31, M61, M89, M107, M127, M521, M607, M1279}</syntaxhighlight> |
||
This version is unbounded (and timed): |
This version is unbounded (and timed): |
||
< |
<syntaxhighlight lang="mathematica">t = SessionTime[]; |
||
For[p = 2, True, p = NextPrime[p], M = 2^p - 1; |
For[p = 2, True, p = NextPrime[p], M = 2^p - 1; |
||
For[i = 1; s = 4, i <= p - 2, i++, s = Mod[s^2 - 2, M]]; |
For[i = 1; s = 4, i <= p - 2, i++, s = Mod[s^2 - 2, M]]; |
||
If[s == 0, Print["M" <> ToString@p]]] |
If[s == 0, Print["M" <> ToString@p]]] |
||
(SessionTime[] - t) {Seconds, Minutes/60, Hours/3600, Days/86400}</ |
(SessionTime[] - t) {Seconds, Minutes/60, Hours/3600, Days/86400}</syntaxhighlight> |
||
I'll see what this gets. |
I'll see what this gets. |
||
Line 2,107: | Line 2,107: | ||
MATLAB suffers from a lack of an arbitrary precision math (bignums) library. |
MATLAB suffers from a lack of an arbitrary precision math (bignums) library. |
||
It also doesn't have great support for 64-bit integer arithmetic...or at least MATLAB 2007 doesn't. So, the best precision we have is doubles; therefore, this script can only find up to M19 and no greater. |
It also doesn't have great support for 64-bit integer arithmetic...or at least MATLAB 2007 doesn't. So, the best precision we have is doubles; therefore, this script can only find up to M19 and no greater. |
||
< |
<syntaxhighlight lang="matlab">function [mNumber,mersennesPrime] = mersennePrimes() |
||
function isPrime = lucasLehmerTest(thePrime) |
function isPrime = lucasLehmerTest(thePrime) |
||
Line 2,141: | Line 2,141: | ||
mersennesPrime = (2.^mNumber) - 1; |
mersennesPrime = (2.^mNumber) - 1; |
||
end</ |
end</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="matlab">[mNumber,mersennesPrime] = mersennePrimes |
||
mNumber = |
mNumber = |
||
Line 2,153: | Line 2,153: | ||
mersennesPrime = |
mersennesPrime = |
||
3 7 31 127 8191 131071 524287</ |
3 7 31 127 8191 131071 524287</syntaxhighlight> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang="maxima">lucas_lehmer(p) := block([s, n, i], |
||
if not primep(p) then false elseif p = 2 then true else |
if not primep(p) then false elseif p = 2 then true else |
||
(s: 4, |
(s: 4, |
||
Line 2,165: | Line 2,165: | ||
sublist(makelist(i, i, 1, 200), lucas_lehmer); |
sublist(makelist(i, i, 1, 200), lucas_lehmer); |
||
/* [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127] */</ |
/* [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127] */</syntaxhighlight> |
||
=={{header|Modula-3}}== |
=={{header|Modula-3}}== |
||
Modula-3 uses L as the literal for <tt>LONGINT</tt>. |
Modula-3 uses L as the literal for <tt>LONGINT</tt>. |
||
< |
<syntaxhighlight lang="modula3">MODULE LucasLehmer EXPORTS Main; |
||
IMPORT IO, Fmt, Long; |
IMPORT IO, Fmt, Long; |
||
Line 2,195: | Line 2,195: | ||
END; |
END; |
||
IO.Put("\n"); |
IO.Put("\n"); |
||
END LucasLehmer.</ |
END LucasLehmer.</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>M2 M3 M5 M7 M13 M17 M19 M31 </pre> |
<pre>M2 M3 M5 M7 M13 M17 M19 M31 </pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import math |
||
proc isPrime(a: int): bool = |
proc isPrime(a: int): bool = |
||
Line 2,223: | Line 2,223: | ||
if isPrime(p) and isMersennePrime(p): |
if isPrime(p) and isMersennePrime(p): |
||
stdout.write " M",p |
stdout.write " M",p |
||
echo ""</ |
echo ""</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> Mersenne primes: |
<pre> Mersenne primes: |
||
Line 2,230: | Line 2,230: | ||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Oz's multiple precision number system use GMP core. |
Oz's multiple precision number system use GMP core. |
||
< |
<syntaxhighlight lang="oz">%% compile : ozc -x <file.oz> |
||
functor |
functor |
||
import |
import |
||
Line 2,293: | Line 2,293: | ||
{Application.exit 0} |
{Application.exit 0} |
||
end</ |
end</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">LL(p)={ |
||
my(m=Mod(4,1<<p-1)); |
my(m=Mod(4,1<<p-1)); |
||
for(i=3,p,m=m^2-2); |
for(i=3,p,m=m^2-2); |
||
Line 2,307: | Line 2,307: | ||
if(LL(p), print("2^"p"-1")) |
if(LL(p), print("2^"p"-1")) |
||
) |
) |
||
};</ |
};</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
int64 is good enough up to M31: |
int64 is good enough up to M31: |
||
< |
<syntaxhighlight lang="pascal">Program LucasLehmer(output); |
||
var |
var |
||
s, n: int64; |
s, n: int64; |
||
Line 2,329: | Line 2,329: | ||
writeln('M', exponent, ' is PRIME!'); |
writeln('M', exponent, ' is PRIME!'); |
||
end; |
end; |
||
end.</ |
end.</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>:> ./LucasLehmer |
<pre>:> ./LucasLehmer |
||
Line 2,344: | Line 2,344: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Using [https://metacpan.org/pod/Math::GMP Math::GMP]: |
Using [https://metacpan.org/pod/Math::GMP Math::GMP]: |
||
< |
<syntaxhighlight lang="perl">use Math::GMP qw/:constant/; |
||
sub is_prime { Math::GMP->new(shift)->probab_prime(12); } |
sub is_prime { Math::GMP->new(shift)->probab_prime(12); } |
||
Line 2,359: | Line 2,359: | ||
foreach my $p (2 .. 43_112_609) { |
foreach my $p (2 .. 43_112_609) { |
||
print "M$p\n" if is_prime($p) && is_mersenne_prime($p); |
print "M$p\n" if is_prime($p) && is_mersenne_prime($p); |
||
}</ |
}</syntaxhighlight> |
||
The ntheory module offers a couple options. This is direct: |
The ntheory module offers a couple options. This is direct: |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/:all/; |
||
$|=1; # flush output on every print |
$|=1; # flush output on every print |
||
my $n = 0; |
my $n = 0; |
||
Line 2,370: | Line 2,370: | ||
print "M$n "; |
print "M$n "; |
||
} |
} |
||
print "\n";</ |
print "\n";</syntaxhighlight> |
||
However it uses knowledge from the thousands of CPU years spent by GIMPS to accelerate results for known values, so doesn't actually run the L-L test until after the 44th value, although code is included for C, Perl, and C+GMP. If we substitute <tt>Math::Prime::Util::GMP::is_mersenne_prime</tt> we can force the test to run. |
However it uses knowledge from the thousands of CPU years spent by GIMPS to accelerate results for known values, so doesn't actually run the L-L test until after the 44th value, although code is included for C, Perl, and C+GMP. If we substitute <tt>Math::Prime::Util::GMP::is_mersenne_prime</tt> we can force the test to run. |
||
A less opaque method uses the modular Lucas sequence, though it has no pretesting other than primality and calculates both <math>U_k</math> and <math>V_k</math> so won't be as fast: |
A less opaque method uses the modular Lucas sequence, though it has no pretesting other than primality and calculates both <math>U_k</math> and <math>V_k</math> so won't be as fast: |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/:all/; |
||
use bigint try=>"GMP,Pari"; |
use bigint try=>"GMP,Pari"; |
||
forprimes { |
forprimes { |
||
Line 2,380: | Line 2,380: | ||
my $mp1 = 2**$p; |
my $mp1 = 2**$p; |
||
print "M$p\n" if $p == 2 || 0 == (lucas_sequence($mp1-1, 4, 1, $mp1))[0]; |
print "M$p\n" if $p == 2 || 0 == (lucas_sequence($mp1-1, 4, 1, $mp1))[0]; |
||
} 43_112_609;</ |
} 43_112_609;</syntaxhighlight> |
||
We can also use the core module <code>Math::BigInt</code>: |
We can also use the core module <code>Math::BigInt</code>: |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="perl">sub is_prime { |
||
my $p = shift; |
my $p = shift; |
||
if ($p == 2) { |
if ($p == 2) { |
||
Line 2,429: | Line 2,429: | ||
} |
} |
||
last if $count >= $upb_count; |
last if $count >= $upb_count; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
Native types work up to M31, after which inaccuracies mean that we need to wheel out gmp. Uses the mod replacement trick from C/FreeBASIC(gmp) |
Native types work up to M31, after which inaccuracies mean that we need to wheel out gmp. Uses the mod replacement trick from C/FreeBASIC(gmp) |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">bool</span> <span style="color: #000000;">full</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- (see extended output below)</span> |
<span style="color: #004080;">bool</span> <span style="color: #000000;">full</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- (see extended output below)</span> |
||
Line 2,489: | Line 2,489: | ||
<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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"completed in %s\n"</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;">"completed in %s\n"</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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,544: | Line 2,544: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de prime? (N) |
||
(or |
(or |
||
(= N 2) |
(= N 2) |
||
Line 2,561: | Line 2,561: | ||
(do (- P 2) |
(do (- P 2) |
||
(setq S (% (- (* S S) 2) MP)) ) |
(setq S (% (- (* S S) 2) MP)) ) |
||
(=0 S) ) ) )</ |
(=0 S) ) ) )</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>: (for N 10000 |
<pre>: (for N 10000 |
||
Line 2,593: | Line 2,593: | ||
be smaller than 1000. |
be smaller than 1000. |
||
< |
<syntaxhighlight lang="pop11">define Lucas_Lehmer_Test(p); |
||
lvars mp = 2**p - 1, sn = 4, i; |
lvars mp = 2**p - 1, sn = 4, i; |
||
for i from 2 to p - 1 do |
for i from 2 to p - 1 do |
||
Line 2,609: | Line 2,609: | ||
endif; |
endif; |
||
p + 2 -> p; |
p + 2 -> p; |
||
endwhile;</ |
endwhile;</syntaxhighlight> |
||
{{Out}} (obtained in few seconds) |
{{Out}} (obtained in few seconds) |
||
< |
<syntaxhighlight lang="pop11">M2 |
||
M3 |
M3 |
||
M5 |
M5 |
||
Line 2,625: | Line 2,625: | ||
M127 |
M127 |
||
M521 |
M521 |
||
M607</ |
M607</syntaxhighlight> |
||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
This is just a translation of VBScript using [bigint], it could be optimized. |
This is just a translation of VBScript using [bigint], it could be optimized. |
||
Flirt with the girl in the cubicle next door while it runs: |
Flirt with the girl in the cubicle next door while it runs: |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function Get-MersennePrime ([bigint]$Maximum = 4800) |
function Get-MersennePrime ([bigint]$Maximum = 4800) |
||
{ |
{ |
||
Line 2,659: | Line 2,659: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
Get-MersennePrime | Format-Wide {"{0,4}" -f $_} -Column 4 -Force |
Get-MersennePrime | Format-Wide {"{0,4}" -f $_} -Column 4 -Force |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,673: | Line 2,673: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
< |
<syntaxhighlight lang="prolog"> |
||
show(Count) :- |
show(Count) :- |
||
findall(N, limit(Count, (between(2, infinite, N), mersenne_prime(N))), S), |
findall(N, limit(Count, (between(2, infinite, N), mersenne_prime(N))), S), |
||
Line 2,711: | Line 2,711: | ||
N mod D =\= 0, |
N mod D =\= 0, |
||
D2 is D + A, prime(N, D2, As). |
D2 is D + A, prime(N, D2, As). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,721: | Line 2,721: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
PureBasic has no large integer support. Calculations are limited to the range of a signed quad integer type. |
PureBasic has no large integer support. Calculations are limited to the range of a signed quad integer type. |
||
< |
<syntaxhighlight lang="purebasic">Procedure Lucas_Lehmer_Test(p) |
||
Protected mp.q = (1 << p) - 1, sn.q = 4, i |
Protected mp.q = (1 << p) - 1, sn.q = 4, i |
||
For i = 3 To p |
For i = 3 To p |
||
Line 2,745: | Line 2,745: | ||
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>M2 |
<pre>M2 |
||
Line 2,757: | Line 2,757: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python"> |
||
from sys import stdout |
from sys import stdout |
||
from math import sqrt, log |
from math import sqrt, log |
||
Line 2,794: | Line 2,794: | ||
if count >= upb_count: break |
if count >= upb_count: break |
||
print |
print |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
Line 2,801: | Line 2,801: | ||
=== Faster loop without division === |
=== Faster loop without division === |
||
< |
<syntaxhighlight lang="python"> |
||
def isqrt(n): |
def isqrt(n): |
||
if n < 0: |
if n < 0: |
||
Line 2,867: | Line 2,867: | ||
if count >= upb_count: break |
if count >= upb_count: break |
||
print |
print |
||
</syntaxhighlight> |
|||
</lang> |
|||
The main loop may be run much faster using [https://pypi.python.org/pypi/gmpy2 gmpy2] : |
The main loop may be run much faster using [https://pypi.python.org/pypi/gmpy2 gmpy2] : |
||
< |
<syntaxhighlight lang="python">import gmpy2 as mp |
||
def lucas_lehmer(n): |
def lucas_lehmer(n): |
||
Line 2,887: | Line 2,887: | ||
s -= m |
s -= m |
||
s -= two |
s -= two |
||
return mp.is_zero(s)</ |
return mp.is_zero(s)</syntaxhighlight> |
||
With this, one can test all primes below 10^5 in around 24 hours on a Core i5 processor, with only one running thread. |
With this, one can test all primes below 10^5 in around 24 hours on a Core i5 processor, with only one running thread. |
||
Line 2,898: | Line 2,898: | ||
=={{header|R}}== |
=={{header|R}}== |
||
<syntaxhighlight lang="r"> |
|||
<lang r> |
|||
# vectorized approach based on scalar code from primeSieve and mersenne in CRAN package `numbers` |
# vectorized approach based on scalar code from primeSieve and mersenne in CRAN package `numbers` |
||
require(gmp) |
require(gmp) |
||
Line 2,932: | Line 2,932: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(require math) |
(require math) |
||
Line 2,951: | Line 2,951: | ||
(loop 3) |
(loop 3) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
<lang |
<syntaxhighlight lang="raku" line>multi is_mersenne_prime(2) { True } |
||
multi is_mersenne_prime(Int $p) { |
multi is_mersenne_prime(Int $p) { |
||
my $m_p = 2 ** $p - 1; |
my $m_p = 2 ** $p - 1; |
||
Line 2,963: | Line 2,963: | ||
} |
} |
||
.say for (2,3,5,7 … *).hyper(:8degree).grep( *.is-prime ).map: { next unless .&is_mersenne_prime; "M$_" };</ |
.say for (2,3,5,7 … *).hyper(:8degree).grep( *.is-prime ).map: { next unless .&is_mersenne_prime; "M$_" };</syntaxhighlight> |
||
{{out|On my system}} |
{{out|On my system}} |
||
Letting it run for about a minute... |
Letting it run for about a minute... |
||
Line 2,998: | Line 2,998: | ||
REXX won't have a problem with the large number of digits involved, but since it's an interpreted language, |
REXX won't have a problem with the large number of digits involved, but since it's an interpreted language, |
||
<br>such massive number crunching isn't conducive in searching for large primes. |
<br>such massive number crunching isn't conducive in searching for large primes. |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm uses the Lucas─Lehmer primality test for prime powers of 2 (Mersenne primes)*/ |
||
@.=0; @.2=1; @.3=1; @.5=1; @.7=1; @.11=1; @.13=1 /*a partial list of some low primes. */ |
@.=0; @.2=1; @.3=1; @.5=1; @.7=1; @.11=1; @.13=1 /*a partial list of some low primes. */ |
||
!.=@.; !.0=1; !.2=1; !.4=1; !.5=1; !.6=1; !.8=1 /*#'s with these last digs aren't prime*/ |
!.=@.; !.0=1; !.2=1; !.4=1; !.5=1; !.6=1; !.8=1 /*#'s with these last digs aren't prime*/ |
||
Line 3,054: | Line 3,054: | ||
return 'M'? /*return "modified" # (Mersenne index).*/ |
return 'M'? /*return "modified" # (Mersenne index).*/ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1) /*simple pluralizer*/</ |
s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1) /*simple pluralizer*/</syntaxhighlight> |
||
{{out|output|text= when the following is used for input: <tt> 10000 </tt>}} |
{{out|output|text= when the following is used for input: <tt> 10000 </tt>}} |
||
<pre> |
<pre> |
||
Line 3,083: | Line 3,083: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
see "Mersenne Primes :" + nl |
see "Mersenne Primes :" + nl |
||
for p = 2 to 18 |
for p = 2 to 18 |
||
Line 3,100: | Line 3,100: | ||
next |
next |
||
return (sn=0) |
return (sn=0) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|RPL}}== |
=={{header|RPL}}== |
||
<syntaxhighlight lang="rpl"> |
|||
<lang RPL> |
|||
%%HP: T(3)A(R)F(.); ; ASCII transfer header |
%%HP: T(3)A(R)F(.); ; ASCII transfer header |
||
\<< DUP LN DUP \pi * 4 SWAP / 1 + UNROT / * IP 2 { 2 } ROT 2 SWAP ; input n; n := Int(n/ln(n)*(1 + 4/(pi*ln(n)))), p:=2; (n ~ number of primes less then n, pi used here only as a convenience), 2 is assumed to be the 1st elemente in the list |
\<< DUP LN DUP \pi * 4 SWAP / 1 + UNROT / * IP 2 { 2 } ROT 2 SWAP ; input n; n := Int(n/ln(n)*(1 + 4/(pi*ln(n)))), p:=2; (n ~ number of primes less then n, pi used here only as a convenience), 2 is assumed to be the 1st elemente in the list |
||
Line 3,111: | Line 3,111: | ||
NEXT NIP ; next i; |
NEXT NIP ; next i; |
||
\>> |
\>> |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Outputs for arguments 130, 607 and 2281, respectively: |
<pre>Outputs for arguments 130, 607 and 2281, respectively: |
||
Line 3,123: | Line 3,123: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def is_prime ( p ) |
||
return true if p == 2 |
return true if p == 2 |
||
return false if p <= 1 || p.even? |
return false if p <= 1 || p.even? |
||
Line 3,155: | Line 3,155: | ||
break if count >= upb_count |
break if count >= upb_count |
||
end |
end |
||
puts</ |
puts</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,162: | Line 3,162: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
extern crate rug; |
extern crate rug; |
||
Line 3,217: | Line 3,217: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
with Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz : |
with Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz : |
||
Less than 8,6 seconds to get the Mersenne primes up to 11213 |
Less than 8,6 seconds to get the Mersenne primes up to 11213 |
||
Line 3,254: | Line 3,254: | ||
{{libheader|Scala}} |
{{libheader|Scala}} |
||
In accordance with definition of Mersenne primes it could only be a Mersenne number with prime exponent. |
In accordance with definition of Mersenne primes it could only be a Mersenne number with prime exponent. |
||
< |
<syntaxhighlight lang="scala">object LLT extends App { |
||
import Stream._ |
import Stream._ |
||
Line 3,274: | Line 3,274: | ||
} |
} |
||
println("That's All Folks!") |
println("That's All Folks!") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} After approx 20 minutes (2.10 GHz dual core) |
{{out}} After approx 20 minutes (2.10 GHz dual core) |
||
<pre style="height: 30ex; overflow: scroll">Finding Mersenne primes in M[2..9999] |
<pre style="height: 30ex; overflow: scroll">Finding Mersenne primes in M[2..9999] |
||
Line 3,302: | Line 3,302: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang="scheme">;;;The heart of the algorithm |
||
(define (S n) |
(define (S n) |
||
(let ((m (- (expt 2 n) 1))) |
(let ((m (- (expt 2 n) 1))) |
||
Line 3,334: | Line 3,334: | ||
(display "M") (display p) (display " ") |
(display "M") (display p) (display " ") |
||
(loop (- i 1) (next-prime p))) |
(loop (- i 1) (next-prime p))) |
||
(loop i (next-prime p)))))</ |
(loop i (next-prime p)))))</syntaxhighlight> |
||
M2 M3 M5 M7 M13... |
M2 M3 M5 M7 M13... |
||
=={{header|Scilab}}== |
=={{header|Scilab}}== |
||
<lang> iexpmax=30 |
<syntaxhighlight lang="text"> iexpmax=30 |
||
n=1 |
n=1 |
||
for iexp=2:iexpmax |
for iexp=2:iexpmax |
||
Line 3,348: | Line 3,348: | ||
end |
end |
||
if s==0 then printf("M%d ",iexp); end |
if s==0 then printf("M%d ",iexp); end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>M2 M3 M5 M7 M13 M17 M19</pre> |
<pre>M2 M3 M5 M7 M13 M17 M19</pre> |
||
Line 3,355: | Line 3,355: | ||
To get maximum speed the program should be [http://seed7.sourceforge.net/scrshots/comp.htm compiled] with -O2. |
To get maximum speed the program should be [http://seed7.sourceforge.net/scrshots/comp.htm compiled] with -O2. |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
include "bigint.s7i"; |
include "bigint.s7i"; |
||
Line 3,408: | Line 3,408: | ||
end while; |
end while; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
Original source: [http://seed7.sourceforge.net/algorith/math.htm#lucasLehmerTest lucasLehmerTest], |
Original source: [http://seed7.sourceforge.net/algorith/math.htm#lucasLehmerTest lucasLehmerTest], |
||
Line 3,421: | Line 3,421: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">func is_mersenne_prime(p) { |
||
return true if (p == 2) |
return true if (p == 2) |
||
var s = 4 |
var s = 4 |
||
Line 3,433: | Line 3,433: | ||
say "M#{n}" |
say "M#{n}" |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,462: | Line 3,462: | ||
Uses a sieve of Eratosthenes. |
Uses a sieve of Eratosthenes. |
||
< |
<syntaxhighlight lang="swift">import BigInt // add package attaswift/BigInt from Github |
||
import Darwin |
import Darwin |
||
Line 3,501: | Line 3,501: | ||
let mprime = BigInt(2).power(prime) - 1 |
let mprime = BigInt(2).power(prime) - 1 |
||
print("2^\(prime) - 1 = \(mprime) is prime") |
print("2^\(prime) - 1 = \(mprime) is prime") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,518: | Line 3,518: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{trans|Pop11}} |
{{trans|Pop11}} |
||
< |
<syntaxhighlight lang="tcl">proc main argv { |
||
set n 0 |
set n 0 |
||
set t [clock seconds] |
set t [clock seconds] |
||
Line 3,552: | Line 3,552: | ||
} |
} |
||
main 33218</ |
main 33218</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
The program was still running, but as the next Mersenne prime is 19937 |
The program was still running, but as the next Mersenne prime is 19937 |
||
Line 3,581: | Line 3,581: | ||
=={{header|TI-83 BASIC}}== |
=={{header|TI-83 BASIC}}== |
||
< |
<syntaxhighlight lang="ti83b">19→M |
||
1→N |
1→N |
||
For(E,2,M) |
For(E,2,M) |
||
Line 3,595: | Line 3,595: | ||
Then:Disp E |
Then:Disp E |
||
End |
End |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 |
<pre>2 |
||
Line 3,607: | Line 3,607: | ||
=={{header|uBasic/4tH}}== |
=={{header|uBasic/4tH}}== |
||
{{Trans|VBScript}} |
{{Trans|VBScript}} |
||
<lang>m = 15 |
<syntaxhighlight lang="text">m = 15 |
||
n = 1 |
n = 1 |
||
For j = 2 To m |
For j = 2 To m |
||
Line 3,620: | Line 3,620: | ||
Next i |
Next i |
||
If s = 0 Then Print "M";j |
If s = 0 Then Print "M";j |
||
Next</ |
Next</syntaxhighlight> |
||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
< |
<syntaxhighlight lang="vb">iexpmax = 15 |
||
n=1 |
n=1 |
||
out="" |
out="" |
||
Line 3,640: | Line 3,640: | ||
End If |
End If |
||
Next |
Next |
||
Wscript.echo out</ |
Wscript.echo out</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>M2 M3 M5 M7 M13 </pre> |
<pre>M2 M3 M5 M7 M13 </pre> |
||
Line 3,646: | Line 3,646: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{works with|Visual Basic .NET|2011}} |
{{works with|Visual Basic .NET|2011}} |
||
< |
<syntaxhighlight lang="vbnet">Public Class LucasLehmer |
||
Private Sub btnGo_Click(sender As Object, e As EventArgs) Handles btnGo.Click |
Private Sub btnGo_Click(sender As Object, e As EventArgs) Handles btnGo.Click |
||
Const iexpmax = 31 |
Const iexpmax = 31 |
||
Line 3,668: | Line 3,668: | ||
Next iexp |
Next iexp |
||
End Sub |
End Sub |
||
End Class</ |
End Class</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 3,676: | Line 3,676: | ||
{{incomplete|Vlang|This seems to hang, something is wrong in the algo.}} |
{{incomplete|Vlang|This seems to hang, something is wrong in the algo.}} |
||
{{trans|go}} |
{{trans|go}} |
||
< |
<syntaxhighlight lang="go">import math.big |
||
const ( |
const ( |
||
primes = [u32(3), 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, |
primes = [u32(3), 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, |
||
Line 3,707: | Line 3,707: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,718: | Line 3,718: | ||
{{libheader|wren-math}} |
{{libheader|wren-math}} |
||
This follows the lines of my Kotlin entry but uses a table to quicken up the checking of the larger numbers. Despite this, it still takes just over 3 minutes to reach M4423. Surprisingly, using ''modPow'' rather than the simple ''%'' operator is even slower. |
This follows the lines of my Kotlin entry but uses a table to quicken up the checking of the larger numbers. Despite this, it still takes just over 3 minutes to reach M4423. Surprisingly, using ''modPow'' rather than the simple ''%'' operator is even slower. |
||
< |
<syntaxhighlight lang="ecmascript">import "/big" for BigInt |
||
import "/math" for Int |
import "/math" for Int |
||
import "io" for Stdout |
import "io" for Stdout |
||
Line 3,754: | Line 3,754: | ||
} |
} |
||
} |
} |
||
System.print("\nTook %(System.clock - start) seconds.")</ |
System.print("\nTook %(System.clock - start) seconds.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,765: | Line 3,765: | ||
{{libheader|Wren-gmp}} |
{{libheader|Wren-gmp}} |
||
Same approach as the CLI version but now uses GMP. Far quicker, of course, as we can now check up to M110503 in less time than before. |
Same approach as the CLI version but now uses GMP. Far quicker, of course, as we can now check up to M110503 in less time than before. |
||
< |
<syntaxhighlight lang="ecmascript">import "./gmp" for Mpz |
||
import "./math" for Int |
import "./math" for Int |
||
Line 3,801: | Line 3,801: | ||
} |
} |
||
} |
} |
||
System.print("\nTook %(System.clock - start) seconds.")</ |
System.print("\nTook %(System.clock - start) seconds.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,812: | Line 3,812: | ||
=={{header|Zig}}== |
=={{header|Zig}}== |
||
Zig supports 128 bit integer types natively, which means it's possible to find all Mersenne primes up to M127. (requires writing a modmul() routine to compute (a * b) % m for 128 bit integers without overflow.) |
Zig supports 128 bit integer types natively, which means it's possible to find all Mersenne primes up to M127. (requires writing a modmul() routine to compute (a * b) % m for 128 bit integers without overflow.) |
||
<syntaxhighlight lang="zig"> |
|||
<lang Zig> |
|||
const std = @import("std"); |
const std = @import("std"); |
||
const stdout = std.io.getStdOut().outStream(); |
const stdout = std.io.getStdOut().outStream(); |
||
Line 3,863: | Line 3,863: | ||
return r; |
return r; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 3,871: | Line 3,871: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Using [[Extensible prime generator#zkl]] and the GMP library. |
Using [[Extensible prime generator#zkl]] and the GMP library. |
||
< |
<syntaxhighlight lang="zkl">var [const] BN=Import.lib("zklBigNum"); // lib GMP |
||
primes:=Utils.Generator(Import("sieve").postponed_sieve); |
primes:=Utils.Generator(Import("sieve").postponed_sieve); |
||
fcn isMersennePrime(p){ |
fcn isMersennePrime(p){ |
||
Line 3,878: | Line 3,878: | ||
s:=BN(4); do(p-2){ s.mul(s).sub(2).mod(mp) } // the % REALLY cuts down on mem usage |
s:=BN(4); do(p-2){ s.mul(s).sub(2).mod(mp) } // the % REALLY cuts down on mem usage |
||
return(s==0); |
return(s==0); |
||
}</ |
}</syntaxhighlight> |
||
Calculating S(n) is done in place (overwriting the value in the BigInt with the result); this really cuts down on memory usage. |
Calculating S(n) is done in place (overwriting the value in the BigInt with the result); this really cuts down on memory usage. |
||
< |
<syntaxhighlight lang="zkl">mersennePrimes:=primes.tweak(fcn(p){ isMersennePrime(p) and p or Void.Skip }); |
||
println("Mersenne primes:"); |
println("Mersenne primes:"); |
||
foreach mp in (mersennePrimes) { print(" M",mp); }</ |
foreach mp in (mersennePrimes) { print(" M",mp); }</syntaxhighlight> |
||
This will "continuously" spew out Mersenne Primes. |
This will "continuously" spew out Mersenne Primes. |
||
Line 3,895: | Line 3,895: | ||
Using five threads: |
Using five threads: |
||
< |
<syntaxhighlight lang="zkl">ps,mpOut := Thread.Pipe(),Thread.Pipe(); // how the threads will communicate |
||
fcn(ps){ // a thread to generate primes, sleeps most of the time |
fcn(ps){ // a thread to generate primes, sleeps most of the time |
||
Utils.Generator(Import("sieve").postponed_sieve).pump(ps) |
Utils.Generator(Import("sieve").postponed_sieve).pump(ps) |
||
Line 3,904: | Line 3,904: | ||
} |
} |
||
println("Mersenne primes:"); |
println("Mersenne primes:"); |
||
foreach mp in (mpOut) { print(" M",mp); }</ |
foreach mp in (mpOut) { print(" M",mp); }</syntaxhighlight> |
||