99 questions/Solutions/39
From HaskellWiki
(Difference between revisions)
m (correction) |
|||
| Line 3: | Line 3: | ||
Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. | Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. | ||
| - | Solution 1: | + | '''Solution 1:''' |
<haskell> | <haskell> | ||
primesR :: Integral a => a -> a -> [a] | primesR :: Integral a => a -> a -> [a] | ||
| Line 11: | Line 11: | ||
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. | 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: | + | '''Solution 2:''' |
<haskell> | <haskell> | ||
primes :: Integral a => [a] | primes :: Integral a => [a] | ||
| Line 23: | Line 23: | ||
Another way to compute the claimed list is done by using the ''Sieve of Eratosthenes''. The <code>primes</code> function generates a list of all (!) prime numbers using this algorithm and <code>primesR</code> 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 :)] | Another way to compute the claimed list is done by using the ''Sieve of Eratosthenes''. The <code>primes</code> function generates a list of all (!) prime numbers using this algorithm and <code>primesR</code> 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 :)] | ||
| - | Solution 3: | + | '''Solution 3:''' |
| - | Use the proper Sieve of Eratosthenes from e.g. [http://www.haskell.org/haskellwiki/99_questions/Solutions/31 31st question's solution] (instead of the above sieve of Turner), adjusted to start its multiples production from the given start point: | + | Use the ''proper'' Sieve of Eratosthenes from e.g. [http://www.haskell.org/haskellwiki/99_questions/Solutions/31 31st question's solution] (instead of the above sieve of Turner), adjusted to start its multiples production from the given start point: |
<haskell> | <haskell> | ||
{-# OPTIONS_GHC -O2 -fno-cse #-} | {-# OPTIONS_GHC -O2 -fno-cse #-} | ||
| Line 71: | Line 71: | ||
(54,893,566 reductions, 79,935,263 cells, 6 garbage collections) | (54,893,566 reductions, 79,935,263 cells, 6 garbage collections) | ||
| - | > filter isPrime [10100..10200] | + | > filter isPrime [10100..10200] -- Sol.1 |
[10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] | [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] | ||
| - | (34,694 reductions, 55,146 cells) | + | (34,694 reductions, 55,146 cells) -- isPrime: Q.31-Sol.1 using primesTME |
| + | (18,880 reductions, 32,596 cells) -- isPrime: Q.31-Sol.2 using Q.35's | ||
| + | -- primeFactors using primesTME | ||
</haskell> | </haskell> | ||
(testing with Hugs of Nov 2002). | (testing with Hugs of Nov 2002). | ||
Revision as of 07:11, 1 June 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 :)]
Solution 3:
Use the proper Sieve of Eratosthenes from e.g. 31st question's solution (instead of the above sieve of Turner), adjusted to start its multiples production from the given start point:
{-# OPTIONS_GHC -O2 -fno-cse #-} -- tree-merging Eratosthenes sieve, primesTME of haskellwiki/prime_numbers, -- adjusted to produce primes in a given range primesR a b | b<a || b<2 = [] | otherwise = (if a <= 2 then [2] else []) ++ gaps a' (join [[x,x+step..b] | p <- takeWhile (<= z) (tail primesTME) , let q = p*p ; step = 2*p x = if a' <= q then q else let r = rem (a'-q) step in if r==0 then a' else a'-r+step ]) where a' = if a<=3 then 3 else (if even a then a+1 else a) z = floor $ sqrt $ fromIntegral b + 1 join (xs:t) = union xs (join (pairs t)) join [] = [] pairs (xs:ys:t) = (union xs ys) : pairs t pairs t = t gaps k xs@(x:t) | k==x = gaps (k+2) t | True = k : gaps (k+2) xs gaps k [] = [k,k+2..b] -- duplicates-removing union of two ordered increasing lists union (x:xs) (y:ys) = case (compare x y) of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys union a b = a ++ b
(This turned out to be quite a project, with a few quite subtle points.) It should be much better then taking a slice of a full sequential list of primes, as it won't try to generate any primes between the square root of b and a. To wit,
> primesR 10100 10200 -- Sol.3 [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] (6,038 reductions, 11,986 cells) > takeWhile (<= 10200) $ dropWhile (< 10100) $ primesTME -- TME: of Q.31 [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] (140,313 reductions, 381,058 cells) > takeWhile (<= 10200) $ dropWhile (< 10100) $ sieve [2..] -- Sol.2 where sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ] [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] (54,893,566 reductions, 79,935,263 cells, 6 garbage collections) > filter isPrime [10100..10200] -- Sol.1 [10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193] (34,694 reductions, 55,146 cells) -- isPrime: Q.31-Sol.1 using primesTME (18,880 reductions, 32,596 cells) -- isPrime: Q.31-Sol.2 using Q.35's -- primeFactors using primesTME
(testing with Hugs of Nov 2002).
