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.

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!

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:

Enumerable.Range(1,999).Where(n=>n%3==0||n%5==0).Sum()

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.
http://blog.functionalfun.net/2008/04/project-euler-problem-7-and-10.html

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);
primes.Dump();
Runs in about 200ms for me, however when I change the last line to:
primes.Count().Dump();
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

Cheers!

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

new[]{3,5}.SelectMany(m=>Enumerable.Range(1,999/m),(r,i)=>r*i).Distinct().Sum()

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