[C# Helper]
Index Books FAQ Contact About Rod
[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[Beginning Software Engineering]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Find Mersenne primes in C#

[Find Mersenne primes in C#]

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 the example to experiment with it and to see additional details.

© 2009-2022 Rocky Mountain Computer Consulting, Inc. All rights reserved.