Title: Find Mersenne primes in C#

Mersenne primes are prime numbers of the from 2ⁿ - 1 for some integer n. For example, 2² - 1 = 4 - 1 = 3 and 3 is prime, so 3 is a Mersenne prime.

This example uses a relatively straightforward approach to find Mersenne primes. When you click the Go button, the following code executes.

private void btnGo_Click(object sender, EventArgs e) { lstPrimes.Items.Clear(); Cursor = Cursors.WaitCursor; Refresh(); try { checked { long power = 1; for (int n = 1; n < 63; n++) { // Get the next power of 2. power *= 2; // See if power - 1 is prime. if (IsPrime(power - 1)) { lstPrimes.Items.Add( n.ToString() + ": " + (power - 1).ToString()); Refresh(); } } } } catch { } Cursor = Cursors.Default; }

This code loops through values of n ranging from 1 to 63 and calls the IsMersennePrime method described shortly to see if 2ⁿ - 1 is prime. The code only checks values up to n = 63 because 2⁶⁴ - 1 is too big to fit in a long integer.

The following code shows the IsPrimes method.

// Return true if the number is prime. private bool IsMersennePrime(long number) { // Handle 2 separately. if (number == 2) return true; // See if the number is divisible by odd values up to Sqrt(number). long sqrt = (long)Math.Sqrt(number); for (long i = 3; i < sqrt; i += 2) if (number % i == 0) return false; // If we get here, the number is prime. return true; }

This method determines whether a number is prime, but it is optimized slightly for Mersenne primes. If n ≥ 1, then the value 2ⁿ must be even so the value 2ⁿ - 1 must be odd. For that reason, the code doesn't check to see if the number is divisible by 2. Instead it loops through odd numbers between 3 and the square root of the number. If the number is divisible by any of those values, then the number is not prime.

If the number is not divisible by any of the n considered by the loop, then the number is prime.

The program quickly finds the Mersenne primes up to 2³¹ - 1. For larger values of n, the value 2ⁿ - 1 is large enough that the search slows down and finding 2⁶¹ - 1 takes longer.

To find larger Mersenne primes, you can use the BigInteger structure in the System.Numerics namespace, but the numbers become so large that your search will slow considerably. You'll probably need to switch to a new method is you want to find new Mersenne primes larger than the current largest known value of 2^77,232,917 - 1.

Download the example to experiment with it and to see additional details.