http://www.codinghelmet.com/  

Wear a helmet. Even when coding.

hints > linq-all-primes

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,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

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 long-term 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 real-world 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

webmasters