Commits

Shu Zong Chen committed d7a833e

Solved 5

Comments (0)

Files changed (1)

problems/problem5.hs

+{-
+Problem 5:
+2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
+
+What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
+-}
+
+has_num_of:: Integer -> Integer -> Integer
+_ `has_num_of` 1 = 0
+x `has_num_of` y = if x `mod` y == 0
+                   then
+                     1 + (x `div` y) `has_num_of` y
+                   else
+                     0
+
+sieve':: [Integer] -> [Integer]
+sieve' [] = []
+sieve' poss =
+  let
+    h = head poss
+    t = tail poss
+    new_poss = [y | y <- t, (y `mod` h) /= 0]
+  in
+    h : sieve' new_poss
+
+prime_sieve:: Integer -> [Integer]
+prime_sieve x
+  | x < 2 = []
+  | x == 2 = [2]
+  | otherwise =
+      sieve' [2..x]
+
+max_factors:: Integer -> Integer -> Integer
+max_factors x y = maximum [i `has_num_of` x | i <- [1..y]]
+
+work target = product [x ^ (max_factors x target) | x <- prime_sieve target]
+
+main = print (work 20)
+