Difference between revisions of "99 questions/Solutions/39"
< 99 questions | Solutions
Jump to navigation
Jump to search
m |
|||
Line 14: | Line 14: | ||
<haskell> |
<haskell> |
||
primes :: Integral a => [a] |
primes :: Integral a => [a] |
||
− | primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ] |
+ | primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ] |
+ | in sieve [2..] |
||
primesR :: Integral a => a -> a -> [a] |
primesR :: Integral a => a -> a -> [a] |
Revision as of 05:21, 31 May 2011
(*) A list of prime numbers.
Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.
Solution 1:
primesR :: Integral a => a -> a -> [a]
primesR a b = filter isPrime [a..b]
If we are challenged to give all primes in the range between a and b we simply take all number from a up to b and filter the primes out.
Solution 2:
primes :: Integral a => [a]
primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ]
in sieve [2..]
primesR :: Integral a => a -> a -> [a]
primesR a b = takeWhile (<= b) $ dropWhile (< a) primes
Another way to compute the claimed list is done by using the Sieve of Eratosthenes. The primes
function generates a list of all (!) prime numbers using this algorithm and primesR
filter the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nicely the Sieve of Eratosthenes can be implemented in Haskell :)]