Creating a prime number generator has always been a fairly common programming assignment. It's relatively simple, it demonstrates key concepts like modulus, and it's a great example for some simple optimization.
I decided to see if I could create an iterator method to do this. Here's what I ended up with:
Now, the math: Primes are divisible by themselves, one, and nothing else. So, one way of finding primes would be to check if a number is divisible by any number under it. Simple, but rapidly becomes inefficient. So, what can we do to reduce the number of possible divisors? Well, because any number that can be factored is divisible by it's factors' factors[^{1}], we can remove any numbers that can be factored from our list of divisors.
[^{1}] The idea here is that for any number, we can reduce it to prime factors. For instance, 144 = 2*2*2*2*3*3. There's no need to check to see if it's divisible by four, since it's divisible by two.
The upshot of this is, we just have to test each number to see if it's divisible by any other prime number, since any nonprime number can be reduced down to prime numbers.
Another efficiency increase is to stop checking once we're past the halfway point for a number. For example: 144. The largest possible factor to 144 is 72. Which means we don't need to test any larger numbers, since they can't possibly be prime factors. The same is true for odd numbers.
A third efficiency increase is taking advantage of LINQs lazy evaluation. This line of code:
Doesn't actually create a list of numbers. It's instructions to create a list of numbers; one that can be evaluated at need, but won't be until needed. It says, start with primes. For each prime, if it is less than maxF and if it is a factor of i, keep it. Otherwise, skip it. So, results holds the instructions to create a list of all factors of i. The next line:
Will evaluate exactly as much as necessary to determine if there are any values in the sequence. So it goes back to the instructions, and works through each one until one fits. If it does, it stops evaluating and exits.
If it gets through every value without any matching the pattern, then we know that we've found a prime number. We add it to our list of primes, and yield it.
The result of this is that not only can we create a list of primes to whatever number we want (theoretically speaking, of course there are real life limits like size and runtime), the list is evaluated lazily itself, so we never have to figure any primes higher than the largest one we want.
For instance:
Will output the first 5000 primes to the console. Surprisingly fast, too. On my system (which is pretty crappy) it takes about .4 seconds to calculate the 5000th prime.
It only takes 1.5 seconds to find the 10,000th prime. And you can verify it too!
http://www.wolframal...i=10000th+prime
Have fun with it.
I decided to see if I could create an iterator method to do this. Here's what I ended up with:
/// <summary> /// Creates a nonterminating IEnumerable of all prime numbers /// greater than or equal to the provided parameter. /// </summary> /// <param name="i"> /// Return all primes greater than or equal to the parameter. /// Defaults to zero.</param> /// <returns>a nonterminating IEnumerable of all prime numbers</returns> static IEnumerable<int> Primes(int i = 0) { List<int> primes = new List<int>(); while (true) { if (i <= 1) i++; else if (i == 2) { primes.Add(i); yield return i++; } else { int maxF = i / 2; var results = primes.Where(j => j <= maxF && i % j == 0); if (results.Any()) i++; else { primes.Add(i); yield return i++; } } } }
Now, the math: Primes are divisible by themselves, one, and nothing else. So, one way of finding primes would be to check if a number is divisible by any number under it. Simple, but rapidly becomes inefficient. So, what can we do to reduce the number of possible divisors? Well, because any number that can be factored is divisible by it's factors' factors[^{1}], we can remove any numbers that can be factored from our list of divisors.
[^{1}] The idea here is that for any number, we can reduce it to prime factors. For instance, 144 = 2*2*2*2*3*3. There's no need to check to see if it's divisible by four, since it's divisible by two.
The upshot of this is, we just have to test each number to see if it's divisible by any other prime number, since any nonprime number can be reduced down to prime numbers.
Another efficiency increase is to stop checking once we're past the halfway point for a number. For example: 144. The largest possible factor to 144 is 72. Which means we don't need to test any larger numbers, since they can't possibly be prime factors. The same is true for odd numbers.
A third efficiency increase is taking advantage of LINQs lazy evaluation. This line of code:
var results = primes.Where(j => j <= maxF && i % j == 0);
Doesn't actually create a list of numbers. It's instructions to create a list of numbers; one that can be evaluated at need, but won't be until needed. It says, start with primes. For each prime, if it is less than maxF and if it is a factor of i, keep it. Otherwise, skip it. So, results holds the instructions to create a list of all factors of i. The next line:
if (results.Any())
Will evaluate exactly as much as necessary to determine if there are any values in the sequence. So it goes back to the instructions, and works through each one until one fits. If it does, it stops evaluating and exits.
If it gets through every value without any matching the pattern, then we know that we've found a prime number. We add it to our list of primes, and yield it.
The result of this is that not only can we create a list of primes to whatever number we want (theoretically speaking, of course there are real life limits like size and runtime), the list is evaluated lazily itself, so we never have to figure any primes higher than the largest one we want.
For instance:
var pr = Primes().Take(5000); pr.ForEach(Console.WriteLine);
Will output the first 5000 primes to the console. Surprisingly fast, too. On my system (which is pretty crappy) it takes about .4 seconds to calculate the 5000th prime.
It only takes 1.5 seconds to find the 10,000th prime. And you can verify it too!
http://www.wolframal...i=10000th+prime
Have fun with it.
4 Comments On This Entry
Page 1 of 1
MATTtheSEAHAWK
20 April 2011  04:27 PM
Great blog post. I worked on this a long time ago but I could never find a very efficient method. Thanks and if I could give rep I would.
Momerath
17 August 2012  01:44 AM
You can speed up the evaluation by changing line 19 to
You can also change your increment to be by 2 and just check odd numbers.
Also, including the parameter in the Enumerable breaks your code. Try it with 15 and see what it says.
int maxF = (int)Math.Sqrt(i);
You can also change your increment to be by 2 and just check odd numbers.
Also, including the parameter in the Enumerable breaks your code. Try it with 15 and see what it says.
sepp2k
17 August 2012  08:37 AM
Note that the <= maxF check in the Where condition won't actually help performance because it won't stop iterating once that check is false. It will still go over all the items in primes (assuming the current number is prime  otherwise it will stop as soon as it finds a factor of course).
To get the behavior you want, you should put it in a TakeWhile instead (because TakeWhile stops iterating as soon as the condition is false).
To get the behavior you want, you should put it in a TakeWhile instead (because TakeWhile stops iterating as soon as the condition is false).
Skydiver
17 August 2012  05:40 PM
I should have gotten to this tab earlier. I'd clicked on the link and just opened the tab in the background. I now realize that this implements the same thing I posted at: http://www.dreaminco...ost__p__1686606
Anyway, there is a bug in the code above. Calling Primes(4) will return 4 as a prime number because the list of primes is no seeded with primes below the incoming parameter i.
Anyway, there is a bug in the code above. Calling Primes(4) will return 4 as a prime number because the list of primes is no seeded with primes below the incoming parameter i.
Page 1 of 1
Trackbacks for this entry [ Trackback URL ]
Recent Entries
Recent Comments
2 user(s) viewing
