7 ms·

Implementing the Sieve of Eratosthenes with Functional Programming

12 points by llambda 13y ago

ColinWright 13y ago
Let's see if this submission gets more attention than when I submitted it just two months ago: https://news.ycombinator.com/item?id=5278887 https://news.ycombinator.com/item?id=5278887 That got two upvotes, and no comments.
ciderpunx 13y ago
Nice implementation. I should check out allong.es. 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/ 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]
- jjaredsimpson 13y ago
  this isn't a sieve, this is trial division. the runtime performance is very different.
  - gizmo686 13y ago
    It is a sieve. Looking at what the function 'sieve' does: 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.
    - minopret 13y ago
      The disadvantage is how many times the implementation using "mod" is visiting each candidate. This disadvantage is explained at length in "The Genuine Sieve of Eratothenes" (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf preprint of http://dx.doi.org/10.1017%2FS0956796808007004 http://dx.doi.org/10.1017%2FS0956796808007004).
- minopret 13y ago
  Now let's imagine you want the first 65,000 primes so you can initialize a primality testing algorithm for RSA or something. You'll want much better performance. And you can get it without too much trouble. 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 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.
niels_olson 13y ago
I'm just learning programming, I'm on Project Euler #9 and have just become familiar with the Sieve of Eratosthenes. Thanks for posting this.
fabriceleal 13y ago
I tried to implement this for project Euler using Clojure, but got hit in the face with stack overflows. Most likely I was doing something naive. Ended up using C.
digitalzombie 13y ago
https://github.com/mythicalprogrammer/ProjectEulerInErlang/blob/problem3/3_largest_prime_factor/mathalchemy.erl https://github.com/mythicalprogrammer/ProjectEulerInErlang/b... in Erlang. Stopped at problem 3 because Erlang is not for numerical crunching... >___<
- mc_ 13y ago
  I found the Euler problems to be illuminating in Erlang. Its been several years now, but I had a decent primes module (https://github.com/jamesaimonetti/ProjectEuler/blob/master/primes.erl https://github.com/jamesaimonetti/ProjectEuler/blob/master/p...) going that seemed fairly performant at the time. 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).

12 points by llambda 13y ago

Let's see if this submission gets more attention than when I submitted it just two months ago: https://news.ycombinator.com/item?id=5278887 https://news.ycombinator.com/item?id=5278887 That got two upvotes, and no comments.

ciderpunx 13y ago

Nice implementation. I should check out allong.es. 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/ 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]

jjaredsimpson 13y ago
this isn't a sieve, this is trial division. the runtime performance is very different.
- gizmo686 13y ago
  It is a sieve. Looking at what the function 'sieve' does: 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.
  - minopret 13y ago
    The disadvantage is how many times the implementation using "mod" is visiting each candidate. This disadvantage is explained at length in "The Genuine Sieve of Eratothenes" (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf preprint of http://dx.doi.org/10.1017%2FS0956796808007004 http://dx.doi.org/10.1017%2FS0956796808007004).
minopret 13y ago
Now let's imagine you want the first 65,000 primes so you can initialize a primality testing algorithm for RSA or something. You'll want much better performance. And you can get it without too much trouble. 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 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.

niels_olson 13y ago

I'm just learning programming, I'm on Project Euler #9 and have just become familiar with the Sieve of Eratosthenes. Thanks for posting this.

fabriceleal 13y ago

I tried to implement this for project Euler using Clojure, but got hit in the face with stack overflows. Most likely I was doing something naive. Ended up using C.

digitalzombie 13y ago

https://github.com/mythicalprogrammer/ProjectEulerInErlang/blob/problem3/3_largest_prime_factor/mathalchemy.erl https://github.com/mythicalprogrammer/ProjectEulerInErlang/b... in Erlang. Stopped at problem 3 because Erlang is not for numerical crunching... >___<

mc_ 13y ago
I found the Euler problems to be illuminating in Erlang. Its been several years now, but I had a decent primes module (https://github.com/jamesaimonetti/ProjectEuler/blob/master/primes.erl https://github.com/jamesaimonetti/ProjectEuler/blob/master/p...) going that seemed fairly performant at the time. 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).