Skip to content

Instantly share code, notes, and snippets.

@rofr
Created June 24, 2013 07:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rofr/5848438 to your computer and use it in GitHub Desktop.
Save rofr/5848438 to your computer and use it in GitHub Desktop.
Just discovered the dotnet BigInteger type. Nice use of implicit type conversion and operator overloading.
/// <summary>
/// Primality test of mersenne prime using the lucas-lehmer test
/// </summary>
/// <param name="p">A prime number</param>
/// <returns>true if 2^p-1 is prime, otherwise false</returns>
public static bool IsMersennePrime(int p)
{
BigInteger mp = BigInteger.Pow(2, p) - 1;
BigInteger n = 4;
for (int i = 1; i < p - 1; i++)
{
n = (n * n - 2) % mp;
}
return n == 0;
}
public static void Main(String[] args)
{
Console.WriteLine(IsMersennePrime(2));
Console.WriteLine(IsMersennePrime(3));
Console.WriteLine(IsMersennePrime(5));
Console.WriteLine(IsMersennePrime(7));
Console.WriteLine(IsMersennePrime(11));
Console.WriteLine(IsMersennePrime(13));
Console.WriteLine(IsMersennePrime(17));
Console.WriteLine(IsMersennePrime(19));
Console.WriteLine(IsMersennePrime(23));
Console.WriteLine(IsMersennePrime(29));
Console.WriteLine(IsMersennePrime(31));
Console.WriteLine(IsMersennePrime(37));
Console.WriteLine(IsMersennePrime(41));
Console.WriteLine(IsMersennePrime(43));
Console.WriteLine(IsMersennePrime(47));
Console.WriteLine(IsMersennePrime(53));
Console.WriteLine(IsMersennePrime(59));
Console.WriteLine(IsMersennePrime(61));
Console.WriteLine(IsMersennePrime(67));
Console.WriteLine(IsMersennePrime(71));
Console.WriteLine(IsMersennePrime(83));
Console.WriteLine(IsMersennePrime(89));
Console.WriteLine(IsMersennePrime(107));
Console.WriteLine(IsMersennePrime(127));
Console.WriteLine(IsMersennePrime(521));
Console.WriteLine(IsMersennePrime(607));
Console.WriteLine(IsMersennePrime(1279));
Console.WriteLine(IsMersennePrime(4253));
Console.WriteLine(IsMersennePrime(19937));
Console.WriteLine(IsMersennePrime(23209));
Console.WriteLine(IsMersennePrime(86243));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment