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 object-oriented and functional design, 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):

Making Your C# Code More Object-Oriented

This course will help leverage your conceptual understanding to produce proper object-oriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More...

Advanced Defensive Programming Techniques

This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More...

Tactical Design Patterns in .NET: Creating Objects

This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More...

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straight-forward as literature implicitly tells us. It is a more engaged process. This course gives an insight to 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...

Writing Highly Maintainable Unit Tests

This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. 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