Find Mersenne primes in C#

[example]

Mersenne primes are prime numbers of the from 2n – 1 for some integer n. For example, 22 – 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 2n – 1 is prime. The code only checks values up to n = 63 because 264 – 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 2n must be even so the value 2n - 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 231 - 1. For larger values of n, the value 2n - 1 is large enough that the search slows down and finding 261 - 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 277,232,917 - 1.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, mathematics and tagged , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.