5 ms·

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

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.

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.