Finding primes using Sieve of Eratosthenes not working - Haskell

Question

Here is the code I am trying to use: This should generate all primes up to 100

sieve_primes = [x | x<-[2..100], y<-[2..50], z <-[2..25], (x*z) `mod` y /= 0]

Answer 1

What you had in mind was probably

Prelude> [x| x<-[2..100], not $ elem x [y*z| y<-[2..50], z<-[2..25]]]
[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]

This is very slow. At least we can rearrange the pieces,

Prelude> [x| let sieve=[y*z| y<-[2..50], z<-[2..25]], 
             x<-[2..100], not $ elem x sieve]
[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]

This is still very slow, for any number much above even 1000 (where you'd use 500 and 250). Then again, why the 25 (250) limit? Your code follows the

primes = [x| x<-[2..], not $ elem x 
                       [y*z| y<-[2..x`div`2], z<-[2..min y (x`div`y)]]]

idea, i.e. y*z = 2*y .. min (y*y) x, so with the known top limit (x <= n) it should be

primesTo n = [x| let sieve=[y*z| y<-[2..n`div`2], z<-[2..min y (n`div`y)]],
                 x<-[2..n], not $ elem x sieve]

(incidentally, max (min y (n/y)) {y=2..n/2} = sqrt n, so we could've used 10 instead of 25, (and 31 instead of 250, for the 1000)).

Now 1000 is not a problem, only above ~ 10,000 we again begin to see that it's slow (still), running at n^2.05..2.10 empirical orders of growth (quick testing interpreted code in GHCi at n = 5000, 10000, 15000).

---

As for your second (now deleted) function, it can be rewritten, step by step improving its speed, as

isPrime n = length [x | x<-[2..n], n `mod` x == 0] == 1
          = take 1 [x | x<-[2..n], n `mod` x == 0] == [n]
          = [x | x<- takeWhile ((<=n).(^2)) [2..n], n `mod` x == 0] == []
          = and [n `mod` x > 0 | x<- takeWhile ((<=n).(^2)) (2:[3,5..n])]

now, compiled, it can get first 10,000 primes in few tenths of a second.

Answer 2

The code

isPrime n = length [x | x<-[2..n], n `mod` x == 0] == 1

computes all the factors just to count them. You don't need to count them: as soon as the second factor is found you can stop your search without checking for further ones.

So, either replace length ... == 1 with a custom predicate, or take 2 elements from the list comprehension before checking its length.