Download or view LucasLehmer.frink in plain text format
// Implements the Lucas-Lehmer test for Mersenne primes.
// This test is sufficient to prove primality.
//
// To be a Mersenne prime, n must be prime. This function does not first
// test that, as it is assumed that some sort of preliminary sieving has
// occurred.
// NOTE:
// As of the 2005-11-12 release of Frink, the isPrime[x] routine automatically
// detects if a number is of the form 2^n-1 and uses this more efficient
// Lucas-Lehmer test, rather than the usual Rabin-Miller tests.
// Returns true if 2^n - 1 is prime, false otherwise.
isMersennePrime[n] :=
{
m = 2^n-1
s = 4
for i = 2 to n-1
s = (modPow[s,2,m] - 2) mod m // modPow[base,exp,m] is base^exp mod m
// Return true (prime) if s is equal to zero, false otherwise.
return s==0
}
Download or view LucasLehmer.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 20143 days, 11 hours, 12 minutes ago.