「HaskellでProject Euler(Problem 1～3)」ブログ用

euler1.hs

euler1 = sumMultiples 1000 [3, 5]

sumMultiples :: Integral a => a -> [a] -> a
sumMultiples _ []   = 0
sumMultiples n muls = foldl1 (+) [x | x <- [1..(n-1)], any (\y -> x `mod` y == 0) muls]

euler2-1.hs

euler2 = sumfib 4000000

sumfib :: Integral a => a -> a
sumfib limit = sumEvenList 0 0
    where
      fibonacci = 1:2:zipWith (+) fibonacci (tail fibonacci)

      sumEvenList  x i = sumEvenList' x (fibonacci !! i) i

      sumEvenList' x y i
        | y > limit      = x
        | y `mod` 2 == 0 = sumEvenList (x + y) (i + 1)
        | otherwise      = sumEvenList x (i + 1)

euler2-2.hs

euler2 = sumfib 4000000

sumfib :: Integral a => a -> a
sumfib limit = sumEvenList 0 0
  where
    fibList 0 = [1]
    fibList 1 = [2, 1]
    fibList n = let list@(fstElem:sndElem:_) = (fibList (n - 1)) in (fstElem + sndElem) : list

    sumEvenList  n i = sumEvenList' n (head (fibList i)) i

    sumEvenList' x y i
      | y > limit      = x
      | y `mod` 2 == 0 = sumEvenList (x + y) (i + 1)
      | otherwise      = sumEvenList x (i + 1)

euler3-1.hs

euler3 = maximum $ factorization 600851475143

factors :: Integer -> [Integer]
factors n = [x | x <- [1..n], n `mod` x == 0]

factorization :: Integer -> [Integer]
factorization 1 = []
factorization x = v : factorization (x `div` v)
  where
    v = (factors x) !! 1

euler3-2.hs

euler3 = maxPrimeFactor 600851475143

maxPrimeFactor :: Integral a => a -> a
maxPrimeFactor n = head $ primeFactors n 2 []
  where
    primeFactors n m list
      | n < m         = list
      | isPrimeFactor = primeFactors (n `div` m) (m + 1) (m:list)
      | otherwise     = primeFactors n (m + 1) (list)
        where isPrimeFactor = not (any (\x -> m `mod` x == 0) list) && n `mod` m == 0

euler3-3.hs

euler3 = maxPrimeFactor 600851475143
 
maxPrimeFactor :: Integral a => a -> a
maxPrimeFactor n = head $ primeFactors n 2 []
  where
    -- 最終的にnを先頭に加えたリストを返して、そのheadを取っているのでnだけ返せば良くこの問題に限ってはlistは不要なはず。(素因数のリストを作るprimeFactors自体は別の問題などでも有用と思われるので一旦残した)
    primeFactors n m list
      | n < m ^ 2     = n:list
      | isPrimeFactor = primeFactors (n `divide` m) (m + 1) (m:list)
      | otherwise     = primeFactors n (m + 1) list
        where
          -- divide関数で割れるだけ割っているので「all (\x -> m `mod` x /= 0)」は不要なはず。(euler3-2 → euler3-4 への思考の流れの備忘のため残した)
          isPrimeFactor = all (\x -> m `mod` x /= 0) list && n `mod` m == 0
          divide n m | r == 0 && q /= 1 = divide q m
                     | otherwise        = n
                       where (q, r) = n `divMod` m

euler3-4.hs

euler3 = maxPrimeFactor 600851475143
 
maxPrimeFactor :: Integral a => a -> a
maxPrimeFactor n = maxPrimeFactor' n 2
  where
    maxPrimeFactor' n m
      | n < m ^ 2    = n
      | divided == 1 = m
      | otherwise    = maxPrimeFactor' divided (m + 1)
        where
          divided = n `divide` m
          divide n m | r == 0    = divide q m
                     | otherwise = n
                       where (q, r) = n `divMod` m