I have the following code that implements the Sieve of Eratosthenes:
primes :: [Int]
primes = primes' [2..]
primes' :: [Int] -> [Int]
primes' [] = []
primes' (p:ps) = p:(primes' [p' | p' <- ps, not (p' `isMultiple` p)])
a `isMultiple` b = (a `mod` b) == 0
main = print (sum (primes' [2..100000]))
I would like to change main to something like
main = print (sum [p | p <- primes, p < 100000]))
Unsurprisingly, this freezes because it must compare p with each element of infinite lists. Since I know that primes are in ascending order, how do I crop an infinite list as soon as I find an item that exceeds my upper limit?
ps Theoretically, primes' filters the input list to return a list of primes. I know there will be some problems if I start the list with something other than 2. I am still working on how to solve this problem myself, so please no spoilers. Thank; -)
source
share