LINQ Expression to Find All Prime Numbers by Zoran Horvat @zoranh75
In previous article titled LINQ Expression to Test If a Number is Prime we have seen that we can test whether a given number is prime by executing the
following LINQ expression:
bool isPrime =
Enumerable.Range(2, (int)Math.Sqrt(number)  1)
.All(divisor => number % divisor != 0);
This expression can be used as part of the larger query which returns a
collection of all prime numbers that can be represented with the variable of
type int. Here is the expression:
IEnumerable<int> primes =
Enumerable.Range(2, Int32.MaxValue  1)
.Where(number =>
Enumerable.Range(2, (int)Math.Sqrt(number)  1)
.All(divisor => number % divisor != 0));
Note that Enumerable.Range is instructed to take all integer numbers between 2 and maximum possible
integer value. Would that be inefficient? Well, no, because none of the numbers
in this particular sequence will be evaluated until actually requested. The
whole sequence of prime numbers and the inner sequence it relies on will be
evaluated lazily, which means that no CPU or memory will be used until needed.
Let's see a couple of examples of using this expression.
Console.WriteLine("First 10 primes");
primes
.Take(10)
.ToList()
.ForEach(prime => Console.WriteLine(prime));
Console.WriteLine("Primes less than 100");
primes
.TakeWhile(p => p < 100)
.ToList()
.ForEach(prime => Console.WriteLine(prime));
Console.WriteLine("There are {0:#,###} primes smaller than 100,000",
primes.TakeWhile(p => p < 100000).Count());
Console.WriteLine("There are {0:#,###} primes smaller than 1,000,000",
primes.TakeWhile(p => p < 1000000).Count());
In all these statements we are querying the sequence of prime numbers until
certain limit is reached  either by counting prime numbers, or by testing them
against the largest prime that we want to take into account. Here is the output
produced by these four queries:
First 10 primes
2
3
5
7
11
13
17
19
23
29
Primes less than 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
There are 9,592 primes smaller than 100,000
There are 78,498 primes smaller than 1,000,000
All the queries except the last one execute in no time. The last statement
takes prime numbers less than one million and it takes a couple of seconds to
evaluate. This particular example demonstrates where is the practical limit of
using this kind of expression. Clearly, evaluation is suitable for smaller sets
of prime numbers, say, up to 100,000.
Let's see a couple more examples that show how this sequence can be used:
var groups =
primes
.TakeWhile(number => number <= 100000)
.GroupBy(number => number 10000)
.Select(group =>
new
{
From = group.Key * 10000,
To = (group.Key + 1) * 10000  1,
Count = group.Count()
});
foreach (var group in groups)
Console.WriteLine("{0,6:#,##0}{1,6:#,###}: {2,6:#,###} primes",
group.From, group.To, group.Count);
This statement prints out total number of prime numbers in the first ten ranges
of 10,000 numbers each. It all becomes clear when we look at the output printed
by this piece of code:
0 9,999: 1,229 primes
10,00019,999: 1,033 primes
20,00029,999: 983 primes
30,00039,999: 958 primes
40,00049,999: 930 primes
50,00059,999: 924 primes
60,00069,999: 878 primes
70,00079,999: 902 primes
80,00089,999: 876 primes
90,00099,999: 879 primes
We could count all the primes from the second thousand, i.e. between numbers
1000 and 1999, inclusive. Here is the statement:
Console.WriteLine("There are {0} primes in the second thousand.",
primes
.SkipWhile(number => number <= 1000)
.TakeWhile(number => number <= 2000)
.Count());
This statement prints:
There are 135 primes in the second thousand.
Next, we could sum up all the prime numbers less than 100,000:
Console.WriteLine("Sum of primes smaller than 100,000 is {0:#,###}",
primes.TakeWhile(number => number < 100000).Sum());
This statement prints:
Sum of primes smaller than 100,000 is 454,396,537
We could apply the same approach to summing up all prime numbers less than a
million. But, this requires 64bit integers, because summation of such large
numbers would quickly end up in integer overflow. Here is the statement which
first converts prime numbers to 64bit integers and only then sums them up:
Int64 sum =
primes
.TakeWhile(number => number < 1000000)
.Select(number => (Int64)number)
.Sum();
Console.WriteLine("Sum of primes smaller than 1,000,000 is {0:#,###}", sum);
This statement produces output:
Sum of primes smaller than 1,000,000 is 37,550,402,023
See also:
Published: Dec 14, 2014
ZORAN HORVAT Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on design patterns, writing unit and integration tests and applying methods to improve code design and longterm maintainability. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video courses at pluralsight.com (requires registration): Tactical Design Patterns in .NET: Managing Responsibilities Applying a design pattern to a realworld problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight into tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More... Tactical Design Patterns in .NET: Control Flow Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More... Improving Testability Through Design This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More... Share this article
