Problem 39 Solutions

primesInRange : Int -> Int -> List Int
primesInRange low high =
    if high < low || high < 2 then
      []
    else
      dropWhile (\x -> x < low) <| primes high


-- find all primes up to n
primes : Int -> List Int
primes n = 
    if n < 2 then
        []
    else
        eratos (List.range 2 n) []


-- sieve of Eratosthenes
-- remove all the the non-primes from a list
eratos : List Int -> List Int -> List Int
eratos candidates primes =  
   case candidates of
       [] -> List.reverse primes

       x::xs ->
           let 
               cs = List.filter (\y -> (y % x) /= 0) xs
           in
               eratos cs (x :: primes)


dropWhile : (a -> Bool) -> List a -> List a
dropWhile predicate list =
    case list of
      []      -> []

      x::xs   -> 
          if (predicate x) then 
              dropWhile predicate xs
          else 
              list

Back to problem