Jacob Carpenter’s Weblog

March 26, 2008

LINQ to prime numbers

Filed under: csharp, Euler, LINQ — Jacob @ 4:41 pm

Having last Friday off, and finding myself in want of something to do, I decided to learn F#. Once I installed F#, though, I learned that desire and motivation are different things.

So I started killing time by solving Project Euler problems. In LINQPad.

(Which you really should download, if you haven’t already.)

People more eloquent than me can explain how embracing constraints helps creativity flourish. I’m not going to try.

Instead, I’ll share a prime number generator inspired by Euler problem 10 and implemented with LINQ:

var odds =
	from n in Enumerable.Range(0, int.MaxValue)
	select 3 + (long) n * 2;

var primes = (new[] { 2L }).Concat(
	from p in odds
	where ! odds.TakeWhile(odd => odd * odd <= p).Any(odd => p % odd == 0)
	select p);

This certainly isn’t the most efficient prime number generator in the world. But the full query to solve the problem (left as a exercise to the reader) runs in a perfectly acceptable less than six seconds on my machine. And it uses no intermediate storage for the primes!

Now that you’ve downloaded LINQPad—you have downloaded LINQPad, haven’t you?—you can start solving Project Euler problems in a blissfully constrained environment, too!

I’ve got Problem 1 down to 54 characters. :-)


  1. 54 characters? The best I can do is:

    (from i in Enumerable.Range(0, 999)
    where i % 3 == 0 || i % 5 == 0
    select i).Sum()

    What do you ahve?

    Comment by Judah — March 27, 2008 @ 11:03 am

  2. Well, for one, you’ve got so much unnecessary whitespace. ;-)

    Here’s mine:


    Comment by jacobcarpenter — March 27, 2008 @ 11:24 am

  3. Oh; it also looks like your answer is off by 999 (which is divisible by 3).

    The lame thing about Enumerable.Range is that the second argument is a sequence length (“count”), rather than an ending number. So your sequence starts at zero and contains 999 elements (ending at 998).

    It sure seems like .Take() could have satisfied the need to limit a range to a specific length, but oh well.

    Comment by jacobcarpenter — March 27, 2008 @ 11:38 am

  4. 53 chars is my best so far.

    new int[1000].Select((n,i)=>i%3==0||i%5==0?i:n).Sum()

    Comment by Todd White — March 28, 2008 @ 1:40 pm

  5. I’ve written up a slightly more efficient prime generator that checks divisibility against previously generated primes rather than odd numbers: it uses a variant of the Unfold operation.

    Comment by Sam Jack — April 21, 2008 @ 12:40 am

  6. I’m not very adept at LINQ, but this had me puzzled.
    var odds =
    from n in Enumerable.Range(0, int.MaxValue)
    select 3 + (long)n * 2;
    var primes = (new[] { 2L }).Concat(
    from p in odds
    where ! odds.TakeWhile(odd => odd * odd p % odd == 0)
    select p);
    Runs in about 200ms for me, however when I change the last line to:
    It takes at least 5 minutes (that’s when I gave up), at full CPU!

    Comment by Fowl — October 19, 2008 @ 3:22 am

  7. Yeah; the prime generator in the post will calculate primes virutally infinitely. LINQPad only shows the first 1000 results in a sequence, when calling .Dump().

    By calling .Count(), you’re trying to count the number of prime numbers the “primes” sequence contains.

    Comment by Jacob — October 20, 2008 @ 7:33 am

  8. use (i%3)*(i%5)==0


    Comment by st0le — July 3, 2010 @ 5:22 am

  9. This is not as short as the other Linq expressions but the algorithm is far more efficient


    Comment by Martin Freedman — February 6, 2015 @ 5:39 am

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Blog at WordPress.com.


Get every new post delivered to your Inbox.

%d bloggers like this: