Implementing the Sieve of Eratosthenes with Functional Programming
raganwald.com
raganwald.com
I got asked "how I would find the prime numbers between 1 and a million" at an interview once. I said "with google" and didn't get the job. I still think that I was right on that one, the first hit on DDG is http://primes.utm.edu/lists/small/millions/ which does the job.
Incidentally you can implement this really nicely in Haskell wher the thunking gets done implicitly so you can say:
primes = 2 : sieve [3,5..]
where
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
And then you can: *Main> take 5 primes
[2,3,5,7,11]In short, my implementation in my Stack Overflow question that follows, using a parameter as counter variable, is not too hard to develop and is much faster. http://stackoverflow.com/questions/16271592
The question that I asked there is how to do the same using stream processing. It's not the first question of its kind there, but it's the one I have at hand. I asked because my search before I asked didn't turn up the others.
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
The input is a list of numbers, the first of which, p, is guaranteed to be prime. The first element of the output is p. Then, we generate a second list, which contains all of the elements of a input list, except for the multiples of p. And we recourse into the second list.
We can make this clear by writing is as:
sieve (p:xs) = p:(sieve $ filter (\x -> x `mod` p /= 0) $ xs)
In this way, we can see that we are selecting the first element in the list, marking it as a prime (by returning it), and then removing all of the multiples of said prime, before repeating the operation on the new list. That is a literal description of the sieving algorithm.
Now, because of lazy evaluation, the sieving function may turn into going through the list one number at a time and performing trial division with all previous primes. From a theoretical perspective, this has the same time complexity (although it would be slower on modern hardware). Using a strict version of filter, the computer (should) literally perform the sieve.
It should be noted that by making sieve strict, you loose the ability to generate an infinite list of primes through sieve [2..], as that would never terminate. I believe the standard solution (as with non functional langauses) is to compute the sieve in blocks, so you solve the block the normal way, then when you get to a new block, you first go through all of your known primes and cross them out.
Edit: If you do try calling sieve (either strictly or non-strictly) on a finite list, you will need to handle the case of an empty list. Adding "sieve []=[]" in addition to the main definition should work.
https://news.ycombinator.com/item?id=5278887
That got two upvotes, and no comments.
in Erlang.
Stopped at problem 3 because Erlang is not for numerical crunching... >___<
Granted, I was still quite the n00b when attempting these problems, so most solutions are probably not optimal, idiomatic, or useful; they were, however, great playgrounds in which to learn about Erlang. I also can't think of any of the problems I have in my repo that ran over the 1-minute time limit. So, I'd say Erlang has plenty of number crunching power for the low hanging problems in Euler (and probably efficient enough for the some of the more advanced ones, though I can't say for sure because I haven't tried them).