Lucas-Lehmer test: Difference between revisions

 

 

=={{header|Ada}}==

with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;

 

end if;

end loop;

Mersenne primes:

M2 M3 M5 M7 M13 M17 M19 M31

 

=={{header|Agena}}==

 

mapm.xdigits(100);

write('M' & i & ' ')

fi

produces:

 

=={{header|ALGOL 68}}==

{{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''}}

 

PROC is prime = ( INT p )BOOL:

count <= upb count

DO SKIP OD

<pre>

Finding Mersenne primes in M[2..33252]:

</pre>

See also: http://www.xs4all.nl/~jmvdveer/mersenne.a68.html

=={{header|AWK}}==

# syntax: GAWK -f LUCAS-LEHMER_TEST.AWK

# converted from Pascal

exit(0)

}

<pre>

Mersenne primes: M2 M3 M5 M7 M13 M17 M19

</pre>

{{works with|BBC BASIC for Windows}}

Using its native arithmetic BBC BASIC can only test up to M23.

PRINT "Mersenne Primes:"

FOR p% = 2 TO 23

sn -= (mp * INT(sn / mp))

NEXT

<pre>

Mersenne Primes:

M17

M19

</pre>

 

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>.

& ( time

= ( print

)

& done

<pre>0,00 0,00 s: M3 is PRIME!

0,00 0,00 s: M5 is PRIME!

1101,12 10491,08 s: M9941 is PRIME!

5618,45 16109,53 s: M11213 is PRIME!</pre>

 

=={{header|C}}==

{{works with|gcc|4.1.2 20070925 (Red Hat 4.1.2-27)}}

{{works with|C99}}

Compiler options: gcc -std=c99 -lm Lucas-Lehmer_test.c -o Lucas-Lehmer_test<br>

#include <stdio.h>

#include <limits.h>

}

printf("\n");

 

Mersenne primes:

M2 M3 M5 M7 M13 M17 M19 M31

 

=={{header|C sharp|C#}}==

{{works with|Visual Studio|2010}}

{{works with|.NET Framework|4.0}}

using System.Collections.Generic;

using System.Numerics;

{

List<int> response = new List<int>();

if (isMersennePrime(i)) response.Add(i);

});

}

}

 

M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213

 

=={{header|Clojure}}==

(cond (< i 4) (>= i 2)

(zero? (rem i 2)) false

(recur (inc n) (rem (- (* s s) 2) mp)))))))

 

Infinite list of Mersenne primes:

(2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253...

 

=={{header|D}}==

{{trans|Python}}

 

if (p < 2 || p % 2 == 0)

return p == 2;

}

 

if (!p.isPrime)

return false;

stdout.flush;

}

{{out}}

<pre>M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 </pre>

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|DWScript}}==

Using Integer type, which is 64bit, limits the search to M31.

var

i, s, m_p : Integer;

Print(' M'+IntToStr(p));

end;

<pre> M2 M3 M5 M7 M13 M17 M19 M31</pre>

 

=={{header|Erlang}}==

-export([main/0]).

 

 

s(MP,1) -> 4 rem MP;

 

In 3 seconds will print

</pre>

Testing larger numbers (i.e. 5000) is possible but will take few minutes.

 

=={{header|F Sharp|F#}}==

Simple arbitrary-precision version:

if n = 1 then 4I % mp else ((s mp (n - 1)) ** 2 - 2I) % mp

 

[ for p in 2..47 do

if p = 2 || s ((1I <<< p) - 1I) (p - 1) = 0I then

 

Tail-recursive version:

if exponent <= 1 then failwith "Exponent must be >= 2"

let prime = 2I ** exponent - 1I;

LucasLehmer 0 4I = 0I

 

Version using library folding function (way shorter and faster than the above):

if exponent <= 1 then failwith "Exponent must be >= 2"

let prime = 2I ** exponent - 1I;

LucasLehmer = 0I

 

=={{header|Fortran}}==

{{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.

IMPLICIT NONE

 

END DO

=={{header|GAP}}==

local i, m, s;

if n = 2 then

 

Filtered([1 .. 2000], LucasLehmer);

 

=={{header|Go}}==

Processing the first list indicates that the test works. Processing the second shows it working on some larger numbers.

 

import (

}

}

{{out}}

<pre>

{{works with|GHC|6.8.2}}

 

where

 

lucasLehmer p = s (2^p-1) (p-1) == 0

 

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 takes about 30 minutes to get up to:

<pre>

 

=={{header|HicEst}}==

DO exponent = 2, 31

IF(exponent > 2) s = 4

ENDDO

 

 

=={{header|J}}==

We use arbitrary-precision integers in order to be able to test any arbitrary prime.

 

public class Mersenne

{

System.out.println();

}

Finding Mersenne primes in M[2..2147483647]:

M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213

 

This version is very speedy and is bounded.

For[i = 1; s = 4, i <= p - 2, i++, s = Mod[s^2 - 2, M]];

If[s == 0, "M" <> ToString@p, p], {p,

Prime /@ Range[300]}], StringQ]

 

 

This version is unbounded (and timed):

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]];

If[s == 0, Print["M" <> ToString@p]]]

 

I'll see what this gets.

=={{header|MATLAB}}==

 

 

function isPrime = lucasLehmerTest(thePrime)

mersennesPrime = (2.^mNumber) - 1;

 

 

mNumber =

mersennesPrime =

 

 

=={{header|Maxima}}==

if not primep(p) then false elseif p = 2 then true else

(s: 4,

 

sublist(makelist(i, i, 1, 200), lucas_lehmer);

 

=={{header|Modula-3}}==

Modula-3 uses L as the literal for <tt>LONGINT</tt>.

 

IMPORT IO, Fmt, Long;

END;

IO.Put("\n");

<pre>M2 M3 M5 M7 M13 M17 M19 M31 </pre>

 

=={{header|Oz}}==

Oz's multiple precision number system use GMP core.

functor

import

{Application.exit 0}

 

=={{header|PARI/GP}}==

my(m=Mod(4,1<<p-1));

for(i=3,p,m=m^2-2);

 

search()={

print("2^2-1");

forprime(p=3,43112609,

)

 

=={{header|Pascal}}==

int64 is good enough up to M31:

var

s, n: int64;

writeln('M', exponent, ' is PRIME!');

end;

<pre>:> ./LucasLehmer

M2 is PRIME!

 

=={{header|Perl}}==

 

my $p = shift;

if ($p == 2) {

}

last if $count >= $upb_count;

 

{{out}}

</pre>

 

=={{header|PicoLisp}}==

(or

(= N 2)

(> N 1)

(bit? 1 N)

 

(de mersenne? (P)

(do (- P 2)

(setq S (% (- (* S S) 2) MP)) )

<pre>: (for N 10000

(and (prime? N) (mersenne? N) (println N)) )

be smaller than 1000.

 

lvars mp = 2**p - 1, sn = 4, i;

for i from 2 to p - 1 do

endif;

p + 2 -> p;

 

M3

M5

M127

M521

=={{header|PureBasic}}==

PureBasic has no large integer support. Calculations are limited to the range of a signed quad integer type.

Protected mp.q = (1 << p) - 1, sn.q = 4, i

For i = 3 To p

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

<pre>M2

M3

 

=={{header|Python}}==

from math import sqrt, log

 

 

count=0

if is_prime(p) and is_mersenne_prime(p):

print("M%d"%p),

count += 1

if count >= upb_count: break

 

<pre> Finding Mersenne primes in M[2..33218]:

M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209</pre>

 

=== Faster loop without division ===

if n < 0:

raise ValueError

return a

a = b

def isprime(n):

if n < 5:

k += 2

return True

def lucas_lehmer_fast(n):

if n == 2:

for i in range(2, n):

sqr = s*s

 

=={{header|Racket}}==

#lang racket

(require math)

 

(loop 3)

 

 

 

 

<pre>

</pre>

 

=={{header|RPL}}==

%%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

NEXT NIP ; next i;

\>>

{{out}}

<pre>Outputs for arguments 130, 607 and 2281, respectively:

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>

 

=={{header|Ruby}}==

return true if p == 2

return false if p <= 1 || p.even?

break if count >= upb_count

end

 

{{out}}

<pre> Finding Mersenne primes in M[2..33218]:

M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209</pre>

 

=={{header|Scala}}==

{{libheader|Scala}}

In accordance with definition of Mersenne primes it could only be a Mersenne number with prime exponent.

import Stream._

 

def s(mp: BigInt, p: Int): BigInt = { if (p == 1) 4 else ((s(mp, p - 1) pow 2) - 2) % mp }

 

println(s"Finding Mersenne primes in M[2..$upbPrime]")

((primes takeWhile (_ <= upbPrime)).par map { p => (p, mersenne(p)) }

}

println("That's All Folks!")

{{out}} After approx 20 minutes (2.10 GHz dual core)

<pre style="height: 30ex; overflow: scroll">Finding Mersenne primes in M[2..9999]

 

=={{header|Scheme}}==

(define (S n)

(let ((m (- (expt 2 n) 1)))

(display "M") (display p) (display " ")

(loop (- i 1) (next-prime p)))

 

M2 M3 M5 M7 M13...

 

=={{header|Seed7}}==

To get maximum speed the program should be [http://seed7.sourceforge.net/scrshots/comp.htm compiled] with -O2.

 

include "bigint.s7i";

end while;

writeln;

 

Original source: [http://seed7.sourceforge.net/algorith/math.htm#lucasLehmerTest lucasLehmerTest],

[http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime]

 

<pre>

Mersenne primes:

M2 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217

</pre>

 

=={{header|Tcl}}==

{{trans|Pop11}}

set n 0

set t [clock seconds]

}

 

<pre> 1: 0s M2

2: 0s M3

22: 655s M9941

23: 3546s M11213</pre>

 

{{omit from|GUISS}}