Rosetta Code

Lucas-Lehmer test: Difference between revisions

Page Discussion

Lucas-Lehmer test (view source)

Revision as of 15:20, 5 May 2024

5,854 bytes added ,  1 month ago
→‎{{header|langur}}
m (BASIC256 and BBC BASIC moved to the BASIC section.)
 
(14 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.
{{works with|langur|0.11}}
I suppose it is theoretically possible to test to the 47th Mersenne prime, as stated in the task description, though it could take a while. As for the limit, it would be very high.
 
<syntaxhighlight lang="langur">val .isPrime = fn(.i) {
With slight syntactic differences, the following would work with earlier versions of langur if you limit it to smaller numbers. 0.8 switched to arbitrary precision.
.i == 2 or .i > 2 and
 
not any(fn .x: .i div .x, pseries 2 .. .i ^/ 2)
<syntaxhighlight lang="langur">val .isPrime = f .i == 2 or
}
.i > 2 and not any f(.x) .i div .x, pseries 2 .. .i ^/ 2
 
val .isMersennePrime = ffn(.p) {
if .p == 2: return true
if not .isPrime(.p): return false
Line 2,103 ⟶ 2,298:
}
 
writeln join " ", map ffn .x: $"M\{{.x;}}", filter .isMersennePrime, series 2300</syntaxhighlight>
</syntaxhighlight>
 
{{out}}
Line 3,239 ⟶ 3,435:
 
=={{header|RPL}}==
===RPL HP-50 series===
<syntaxhighlight lang="rpl">
%%HP: T(3)A(R)F(.); ; ASCII transfer header
Line 3,257 ⟶ 3,454:
These take respectively 1m 22s on the real HP 50g, 4m 29s and 10h 29m 23s on the emulator (Debug4 running on PC under WinXP, Intel(R) Core(TM) Duo CPU T2350 @ 1.86GHz).
</pre>
===RPL HP-28 series===
Unlike RPL implemented on HP-50 series, the first version of the language does not feature big integers, modular arithmetic operators, prime number test functions, nor even modulo operator for unsigned integers.
Let's build them all...
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
'''IF''' { #1 #2 #3 #5 } OVER POS '''THEN''' #1 ≠
'''ELSE IF''' # 1d DUP2 AND ≠ OVER 3 DUP2 / * == OR
'''THEN''' DROP 0
'''ELSE''' DUP B→R √ → divm
≪ 1 SF 4
5 divm '''FOR''' n
'''IF''' OVER n DUP2 / * ==
'''THEN''' 1 CF divm 'n' STO '''END'''
6 SWAP - DUP '''STEP'''
DROP2 1 FS?
≫ '''END END'''
≫ '<span style="color:blue">bPRIM?</span>' STO
≪ → m
≪ #1
'''WHILE''' OVER #0 > '''REPEAT'''
IF OVER #1 AND #1 == '''THEN'''
3 PICK * m / LAST ROT * - '''END'''
SWAP SR SWAP
ROT DUP * m / LAST ROT * - ROT ROT
'''END'''
ROT ROT DROP2
≫ ≫ '<span style="color:blue">MODXP</span>' STO
≪ 2 OVER ^ R→B 1 - → mp
≪ #4
3 ROT '''FOR''' n
#2 mp <span style="color:blue">MODXP</span>
'''IF''' DUP #2 < '''THEN''' mp + '''END''' #2 -
'''NEXT'''
#0 ==
≫ ≫ '<span style="color:blue">MSNP?</span>' STO
≪ { 2 } 3 32 '''FOR''' j
'''IF''' j R→B <span style="color:blue">bPRIM?</span>
'''THEN IF''' j <span style="color:blue">MNSP?</span> '''THEN''' j + '''END END'''
'''NEXT'''
≫ '<span style="color:blue">TASK</span>' STO
|
<span style="color:blue">bPRIM?</span> ''( #a → boolean )''
return 1 if a is 2, 3 or 5 and 0 if a is 1
if 2 or 3 divides a
return 0
else store sqrt(a)
d = 4 ; flag 1 set while presumed prime
for n=5 to sqrt(a)
if d divides a
prepare loop exit
d = 6-d ; n += d
clean stack, return result
<span style="color:blue">MODXP</span> ''( #base #exp #m → #mod(base^exp,m) )''
result = 1;
while (exp > 0) {
if ((exp & 1) > 0)
result = (result * base) % m;
exp >>= 1;
base = (base * base) % m;
}
clean stack, return result
<span style="color:blue">MNSP?</span> ''( p → boolean )''
s0 = 4
loop p-2 times
r = mod(s(n-1)^2 mod Mp
s(n) = (r - 2) mod Mp
return 1 if s(p-2)=0 mod Mp
|}
{{out}}
<pre>
1: { 2 3 5 7 13 17 19 31 }
</pre>
Runs in 48 seconds on a standard HP-28S.
 
=={{header|Ruby}}==
Line 3,854 ⟶ 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="ecmascriptwren">import "./big" for BigInt
import "./math" for Int
import "io" for Stdout
 
Line 3,901 ⟶ 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="ecmascriptwren">import "./gmp" for Mpz
import "./math" for Int
 
Langurmonkey
890

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339878...364251"