View Forum Topic

Forums
CS5035
Question regarding Sieve of Eratosthenes

Author	Message
anemade Posts: 2	Posted 20:11 Feb 15, 2019 \| The given haskell version in assignment :- sieve (p:ps) = p : sieve (filter(\n -> n `mod` p /= 0) ps) primes = 2 : sieve [3, 5 ..] does not actually follow the Sieve of Eratosthenes algorithm. Then how to proceed for the python version with the given 2 function definitions keeping the algorithm in mind?
rabbott Posts: 1649	Posted 21:01 Feb 15, 2019 \| Would you elaborate your question. What is bothering you about the Haskell program? Perhaps more to the point, the intent of the assignment is to give you experience writing generators. Write a Python program that uses generators and that produces an endless stream of primes. Don't use the algorithm that for a given candidate prime you determine whether it is prime by explicitly dividing it by all primes less than or equal to its square root. Your program should (a) generate a stream of numbers such as `count(1)` (or to mimic the Haskell code, `count(3, 2)`), (b) select and `yield` the next prime from that stream, and then (c) continue with the stream that has been modified based on the prime you found. In other words, once you find a prime, modify the stream based on that prime. Look at the Haskell code you quoted in your question. That's what it does. You should do something similar in Python. Last edited by rabbott at 21:06 Feb 15, 2019.
anemade Posts: 2	Posted 21:28 Feb 15, 2019 \| Okay so as you are saying "write a Python version of the sieve of Eratosthenes" and you provided the same in Haskell. From past two days i was wondering about the given haskell version and somewhere i knew it didn't match for what the sieve says instead wherever i read it was like : you are given 'n', make a list from [2, .., n] then iterate the list from 2 to (square root of n) select the first prime 2 (which is known to algo) and strike out the multiples of 2, next you move on to 3 then you have already striked out 6 so you start from 3² = 9 , so you strike it out and further multiples of it. I also found a reference which pretty much gives the close version towards the sieve :. https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf So as far as i understood your reply that you are not specifically looking for Sieve of Eratosthenes rather just what you mentioned in the 3rd para of the reply, right? Last edited by anemade at 21:30 Feb 15, 2019.
rabbott Posts: 1649	Posted 22:04 Feb 15, 2019 \| The O'Neil paper claims that once you find a prime `p`, it is inefficient to test numbers less than `pp` for divisibility by `p`. Yet the sieve as written will test all primes `p1` less than `pp` for divisibility by `p`. That test isn't necessary because if `p1` were divisible by `p`, it would also be divisible by some prime less than `p`. That's true. You could eliminate the extra tests by modifying sieve to be the following. sieve (p:ps) = p : sieve (filter(\n -> n < pp \|\| n `mod` p /= 0) ps) This will work just as well and won't bother testing prime less than, e.g., 49, for divisibility by 7. It will get the correct answer. O'Neill also says that instead of dividing one should generate the stream `[pp, p*(p+1) ..]` and drop all numbers in that stream. That's possible also. It would just require a somewhat more sophisticated program. You can do that if you prefer. Last edited by rabbott at 22:25 Feb 15, 2019.
rabbott Posts: 1649	Posted 22:57 Feb 15, 2019 \| Actually, the approached sketched in the previous comment is not at all hard. It doesn't require an additional stream for each new prime. `sieve` `pnp (n:ns) \| n < pn = n : sieve (nn) n (sieve pn p ns) \| n == pn = sieve pn p ns \| n > pn = sieve (pn+p) p (n:ns)` `primes = 2 : 3 : sieve 9 3 [5, 7 ..]` It generates a stack overflow after prime 73. `> take 25 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73** Exception: stack overflow` The original version didn't do that and returned an almost instantaneous answer for the first 25 primes. `> take 25 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] (0.00 secs, 213,536 bytes)` It's likely the reason for the difference is that the original version used `filter`, which is probably implemented very efficiently whereas this version does its filtering explicitly and with recursion. Last edited by rabbott at 23:16 Feb 15, 2019.
rabbott Posts: 1649	Posted 23:31 Feb 15, 2019 \| Here's a version that uses `filter` and that runs quite quickly. sieve pn p (n:ns) \| n < pn = n : let pns = sieve pn p ns nSeq = [nn, nn + n ..] in filter (\x -> not (x `elem` takeWhile (\y -> y <= x) nSeq) ) pns \| n == pn = sieve pn p ns \| n > pn = sieve (pn+p) p (n:ns) > take 25 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] (0.00 secs, 266,376 bytes) Last edited by rabbott at 23:33 Feb 15, 2019.
apolinarsanchez Posts: 8	Posted 23:32 Feb 15, 2019 \| so I've been stuck on this part for some time: (c) continue with the stream that has been modified based on the prime you found. In other words, once you find a prime, modify the stream based on that prime. If I call sieve(3, inp) with inp = count(3,2), the generator will yield 5, 7, 11, 13, 17, 19, 23, 25 ... - all the odd numbers that are not multiples of 3. If I am understanding correctly, you are saying that from this generator we can take 5 and still have access to the stream 7, 11, 13, 19, 23, 25 ... and eliminate out all multiples of 5 from that stream. How is that possible in python? Last edited by apolinarsanchez at 23:46 Feb 15, 2019.
rabbott Posts: 1649	Posted 23:40 Feb 15, 2019 \| apolinarsanchez wrote: so I've been stuck on this part for some time: (c) continue with the stream that has been modified based on the prime you found. In other words, once you find a prime, modify the stream based on that prime. If I call sieve(3, inp) with inp = count(3,2), the generator will yield 5, 7, 11, 13, 17, 19, 23, 25 ... - all the odd numbers that are not multiples of 3. If I am understanding correctly, you are saying that from this generator we can take 5 and still have access to the stream 7, 11, 13, 19, 23, 25 ... and cross out all multiples of 5 from that stream. How is that possible in python? As you say: inp = count(3,2) # => 3, 5, 7, 9, ... inp = sieve(3, inp) # => 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 inp = sieve(5, inp) # => 7, 11, 13, 17, 19, 23, 29, 31, 37 In other words, apply each successive sieve to the previous sieved stream. Last edited by rabbott at 23:42 Feb 15, 2019.
apolinarsanchez Posts: 8	Posted 00:04 Feb 16, 2019 \| rabbott wrote: apolinarsanchez wrote: so I've been stuck on this part for some time: (c) continue with the stream that has been modified based on the prime you found. In other words, once you find a prime, modify the stream based on that prime. If I call sieve(3, inp) with inp = count(3,2), the generator will yield 5, 7, 11, 13, 17, 19, 23, 25 ... - all the odd numbers that are not multiples of 3. If I am understanding correctly, you are saying that from this generator we can take 5 and still have access to the stream 7, 11, 13, 19, 23, 25 ... and cross out all multiples of 5 from that stream. How is that possible in python? As you say: inp = count(3,2) # => 3, 5, 7, 9, ... inp = sieve(3, inp) # => 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 inp = sieve(5, inp) # => 7, 11, 13, 17, 19, 23, 29, 31, 37 In other words, apply each successive sieve to the previous sieved stream. Thank you.