Numbers are fascinating
I've always been fascinated with numbers. Like the fact that when you add up the digits of any number which is divisible by 9, the sum adds up to either 9 or another number which is divisible by 9.
9 x 678 = 6102
6 + 1 + 0 + 2 = 9
Prime numbers
One evening whilst working away in Scotland, my boss and I were talking about number theory and the subject of prime numbers came up. He told me there are prizes for finding new prime numbers that are hundreds of digits long. He explained to me that they use super computers to search for prime numbers. I hadn't thought much about prime numbers before and I didn't know about this search for them. It captured my imagination and set my mind off wondering how big a prime number I could find.
The challenge
He bet me a bacon sandwich that I couldn't find a 7 digit prime number by the time we met up again in the morning, without cheating. I thought how hard could it be and I accepted the challenge. Surely I could do this. I just needed to write a program and leave it running overnight. I was not going to lose this bet, there was a bacon sandwich riding on it.
What is a prime number?
A prime number is a whole number greater than zero which is only wholly divisible by itself or 1, without leaving a remainder.
Apart from number 2, prime numbers are always odd numbers, because all even numbers can always divide by 2 as well as themselves and 1.
Getting ready for the challenge
I went to the garage over the road to get some supplies for the night ahead and went back to my hotel room to start the search for prime numbers.
I started out by writing the basic logic of what was required, onto paper:
- 2 is the first prime number, but it is even. Start the search from 3 and add 2 each time to it so I am only ever checking odd numbers.
- Check the number is not divisible by any of the prime numbers lower than it.
- Print the number to the screen.
- Keep a record of all of the prime numbers I find so I can leave it running and show my boss the next morning.
Turning this first attempt into code
The below code snippet shows how I was checking for prime numbers.
I have limited the search to be between a start number and end number as it is just an example.
using System;
using System.Collections.Generic;
using System.Linq;
namespace PrimeNumbers
{
public static class PrimeCheck
{
public static void Main()
{
SearchForPrimeNumbers(3, 1000);
}
public static void SearchForPrimeNumbers(long lowestNumberToCheck, long highestNumberToCheck)
{
const long LOWEST_PRIME_NUMBER = 2;
List<long> foundPrimes = new List<long>();
foundPrimes.Add(LOWEST_PRIME_NUMBER);
long numberToCheck = lowestNumberToCheck;
long latestPrimeNumber = foundPrimes.First();
Console.WriteLine("Searching for prime numbers between {0} and {1}", lowestNumberToCheck, highestNumberToCheck);
while (numberToCheck <= highestNumberToCheck)
{
if (IsPrimeNumber(foundPrimes, numberToCheck))
{
foundPrimes.Add(numberToCheck);
Console.WriteLine("Prime number: " + numberToCheck.ToString());
}
numberToCheck = numberToCheck + 2;
}
Console.WriteLine("Longest Prime: {0} - {1} digits", foundPrimes.Last(), foundPrimes.Last().ToString().Length);
}
private static bool IsPrimeNumber(List<long> foundPrimes, long numberToCheck)
{
bool isPrime = true;
foreach (long foundPrime in foundPrimes)
{
if (numberToCheck % foundPrime == 0)
{
isPrime = false;
break;
}
}
return isPrime;
}
}
}You can test this code in your browser on dotnetfiddle here
Results of the challenge
I left the code running for 5 or 6 hours and when I checked it in the morning, I was amazed to to see that not only had I found 7 digit prime numbers, I had also found 8 digit ones.
My boss was very surprised and at first he thought I must have cheated. I showed him the massive table of prime numbers and he conceded that I had won the challenge.
Later that day, on the way to the airport, I realised where I could fine-tune the application to eliminate checks against unnecessary number and make it run even faster.
Improving the algorithm
I was checking if a number was divisible by every prime number lower than it, which was wasting a lot of time.
All I needed to do was test the number against prime numbers which were less than or equal to the square root of the number.
Take 31 for example:
31 / 3 = 10.34
31 / 5 = 6.2
<strong>square root of 31 = 5.57</strong>
31 / 7 = 4.43
31 / 11 = 2.82
31 / 13 = 2.38
31 / 17 = 1.82
31 / 19 = 1.63
31 / 23 = 1.35
31 / 29 = 1.07Look at the number in the middle and the number on the right.
To start with, the number in the middle is lower than the number on the right.
As the number in the middle gets higher than the square root of 31 (which is 5.57), you will notice the number on the right gets lower. We already know it doesn't divide by the numbers lower than the square root as we have already tested 3 and 5.
In this example I was able to find out that the number was prime by just doing 2 checks rather than 9.
We altered the code and it sped through the prime numbers far faster than the previous code. We left it running for a few days and managed to get to a 20 digit prime number.
This might not be very impressive to you, but we were doing this from my personal laptop, which by today's standard's is not very powerful.
Here is the improved code.
using System;
using System.Collections.Generic;
using System.Linq;
namespace PrimeNumbers
{
public static class PrimeCheck
{
public static void Main()
{
SearchForPrimeNumbers(3, 1000);
}
public static void SearchForPrimeNumbers(long lowestNumberToCheck, long highestNumberToCheck)
{
const long LOWEST_PRIME_NUMBER = 2;
List<long> foundPrimes = new List<long>();
foundPrimes.Add(LOWEST_PRIME_NUMBER);
long numberToCheck = lowestNumberToCheck;
long latestPrimeNumber = foundPrimes.First();
Console.WriteLine("Searching for prime numbers between {0} and {1}", lowestNumberToCheck, highestNumberToCheck);
while (numberToCheck <= highestNumberToCheck)
{
long maxPrime = (long)Math.Ceiling(Math.Sqrt(numberToCheck));
if (IsPrimeNumber(foundPrimes, numberToCheck, maxPrime))
{
foundPrimes.Add(numberToCheck);
Console.WriteLine("Prime number: " + numberToCheck.ToString());
}
numberToCheck = numberToCheck + 2;
}
Console.WriteLine("Longest Prime: {0} - {1} digits", foundPrimes.Last(), foundPrimes.Last().ToString().Length);
}
private static bool IsPrimeNumber(List<long> foundPrimes, long numberToCheck, long maxPrime)
{
bool isPrime = true;
foreach (long foundPrime in foundPrimes)
{
if(foundPrime > maxPrime)
{
isPrime = true;
break;
}
else
{
if (numberToCheck % foundPrime == 0)
{
isPrime = false;
break;
}
}
}
return isPrime;
}
}
}You can test this code in your browser on dotnetfiddle here
In my actual program, I got it to store every prime number in a database table, so I was able to stop the search and continue it at a later date.
Why don't you have a play and see what the longest prime number you can find is?
There is another improvement to be made to the code in terms of the maxPrime value. I wonder if you can work it out.
Using this code, the longest prime number I found is a 20 digit one.
If you have any suggestions for improving this algorithm, please put it in the comments, or a link to the dotnetfiddle at least.