LINQ Expression to Find All Prime Numbers

by Zoran Horvat
December 14, 2014

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,000-19,999:  1,033 primes
20,000-29,999:    983 primes
30,000-39,999:    958 primes
40,000-49,999:    930 primes
50,000-59,999:    924 primes
60,000-69,999:    878 primes
70,000-79,999:    902 primes
80,000-89,999:    876 primes
90,000-99,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 64-bit integers, because summation of such large numbers would quickly end up in integer overflow. Here is the statement which first converts prime numbers to 64-bit 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
                
    

---