Lucas-Lehmer test: Difference between revisions
→{{header|langur}}
m (→RPL HP-28 series: typo) |
Langurmonkey (talk | contribs) |
||
| (12 intermediate revisions by 7 users not shown) | |||
Line 581:
M19
</pre>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">let m = 7
let n = 1
for e = 2 to m
if e = 2 then
let s = 0
else
let s = 4
endif
let n = (n + 1) * 2 - 1
for i = 1 to e - 2
let s = (s * s - 2) % n
next i
if s = 0 then
print e, " ",
endif
next e</syntaxhighlight>
{{Out}}
<pre>2 3 5 7 </pre>
=={{header|BCPL}}==
Line 1,170 ⟶ 1,204:
With p up to 10_000 it prints:
<pre>M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9941 </pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function IsMersennePrime(P: int64): boolean;
{Test for Mersenne Prime - P cannot be bigger than 63}
{Because (1 shl 64) would be bigger than in64}
var S,MP: int64;
var I: integer;
begin
if P= 2 then Result:=true
else
begin
MP:=(1 shl P) - 1;
S:=4;
for I:=3 to P do
begin
S:=(S * S - 2) mod MP;
end;
Result:=S = 0;
end;
end;
procedure ShowMersennePrime(Memo: TMemo);
var Sieve: TPrimeSieve;
var I: integer;
begin
{Create Sieve}
Sieve:=TPrimeSieve.Create;
{Test cannot handle values bigger than 64}
Sieve.Intialize(64);
for I:=0 to Sieve.PrimeCount-1 do
if IsMersennePrime(Sieve.Primes[I]) then
begin
Memo.Lines.Add(IntToStr(Sieve.Primes[I]));
end;
Sieve.Free;
end;
</syntaxhighlight>
{{out}}
<pre>
2
3
5
7
13
17
19
31
Elapsed Time: 10.167 ms.
</pre>
=={{header|DWScript}}==
Line 1,201 ⟶ 1,296:
{{Out}}
<pre> M2 M3 M5 M7 M13 M17 M19 M31</pre>
=={{header|EasyLang}}==
{{trans|BASIC256}}
<syntaxhighlight>
write "Mersenne Primes: "
func lulehm p .
mp = bitshift 1 p - 1
sn = 4
for i = 2 to p - 1
sn = sn * sn - 2
sn = sn - (mp * (sn div mp))
.
return if sn = 0
.
for p = 2 to 23
if lulehm p = 1
write "M" & p & " "
.
.
</syntaxhighlight>
{{out}}
<pre>
Mersenne Primes: M3 M5 M7 M13 M17 M19
</pre>
=={{header|EchoLisp}}==
Line 1,460 ⟶ 1,580:
END PROGRAM LUCAS_LEHMER</syntaxhighlight>
===128 Bit Version===
This version can find all Mersenne Primes up to M127. Its based on the Zig code but written in Fortran 77 style (fixed format, unstructured loops.) Works with GNU Fortran which has 128 bit integer support.
<syntaxhighlight lang="fortran">
PROGRAM Mersenne Primes
IMPLICIT INTEGER (a-z)
LOGICAL is mersenne prime
PARAMETER (sz primes = 31)
INTEGER*1 primes(sz primes)
DATA primes
& /2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
& 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
& 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
& 127/
PRINT *, 'These Mersenne numbers are prime:'
DO 10 i = 1, sz primes
p = primes(i)
10 IF (is mersenne prime(p))
& WRITE (*, '(I5)', ADVANCE = 'NO'), p
PRINT *
END
FUNCTION is mersenne prime(p)
IMPLICIT NONE
LOGICAL is mersenne prime
INTEGER*4 p, i
INTEGER*16 n, s, modmul
IF (p .LT. 3) THEN
is mersenne prime = p .EQ. 2
ELSE
n = 2_16**p - 1
s = 4
DO 10 i = 1, p - 2
s = modmul(s, s, n) - 2
10 IF (s .LT. 0) s = s + n
is mersenne prime = s .EQ. 0
END IF
END
FUNCTION modmul(a0, b0, m)
IMPLICIT INTEGER*16 (a-z)
modmul = 0
a = MODULO(a0, m)
b = MODULO(b0, m)
10 IF (b .EQ. 0) RETURN
IF (MOD(b, 2) .EQ. 1) THEN
IF (a .LT. m - modmul) THEN
modmul = modmul + a
ELSE
modmul = modmul - m + a
END IF
END IF
b = b / 2
IF (a .LT. m - a) THEN
a = a * 2
ELSE
a = a - m + a
END IF
GO TO 10
END
</syntaxhighlight>
{{Out}}
<pre>
These Mersenne numbers are prime:
2 3 5 7 13 17 19 31 61 89 107 127
</pre>
=={{header|FreeBASIC}}==
Line 2,085 ⟶ 2,281:
=={{header|langur}}==
{{trans|D}}
It is theoretically possible to test to the 47th Mersenne prime, as stated in the task description, but it could take a while. As for the limit, it would be extremely high.
<syntaxhighlight lang="langur">val .isPrime = fn(.i) {
.i == 2 or .i > 2 and
not any(fn .x: .i div .x, pseries 2 .. .i ^/ 2)
}
val .isMersennePrime =
if .p == 2: return true
if not .isPrime(.p): return false
Line 2,103 ⟶ 2,298:
}
writeln join " ", map
</syntaxhighlight>
{{out}}
Line 3,259 ⟶ 3,455:
</pre>
===RPL HP-28 series===
Unlike RPL implemented on HP-50 series,
Let's build them all...
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
Line 3,279 ⟶ 3,475:
DROP2 1 FS?
≫ '''END END'''
≫
≪ → m
Line 3,290 ⟶ 3,486:
'''END'''
ROT ROT DROP2
≫ ≫
≪ 2 OVER ^ R→B 1 - → mp
≪ #4
3 ROT '''FOR''' n
#2 mp
'''IF''' DUP #2 < '''THEN''' mp + '''END''' #2 -
'''NEXT'''
#0 ==
≫ ≫
≪ { 2 } 3 32 '''FOR''' j
'''IF''' j R→B
'''THEN IF''' j <span style="color:blue">MNSP?</span> '''
'''NEXT'''
≫
|
return 1 if a is 2, 3 or 5 and 0 if a is 1
if 2 or 3 divides a
Line 3,321 ⟶ 3,517:
result = 1;
while (exp > 0) {
Line 3,332 ⟶ 3,528:
s0 = 4
loop p-2 times
Line 3,949 ⟶ 4,145:
{{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.
<syntaxhighlight lang="
import "./math" for Int
import "io" for Stdout
Line 3,996 ⟶ 4,192:
{{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.
<syntaxhighlight lang="
import "./math" for Int
| |||