Skip to content
Newer
Older
100644 27 lines (22 sloc) 807 Bytes
92284ca Problems 1-6,8-9
Eric Wilson authored Jan 4, 2011
1 {--
2 There must be a better way.
3 Sorry this is unreadable, and resorts to using Integer.
4 --}
5
6 isPrime :: Integer -> Bool
7 isPrime = null . smallFactors
8
9 smallFactors :: Integer -> [Integer]
10 smallFactors n = takeWhile (\d -> d*d <= n) $ factors n
11 where factors n = [ d | d <- [2..n-1], mod n d == 0]
12
13 smallPrimeFactors :: Integer -> [Integer]
14 smallPrimeFactors = filter isPrime . smallFactors
15
16 reduceByList :: Integer -> [Integer] -> Integer
17 reduceByList big [] = big
18 reduceByList big (div:divs) = reduceByList (reduce big div) divs
19 where reduce num div =
20 if mod num div /= 0
21 then num
22 else reduce (quot num div) div
23
24 euler3 :: Integer -> Integer
25 euler3 n = if reduceByList n (smallPrimeFactors n) == 1
26 then last (smallPrimeFactors n)
27 else reduceByList n (smallPrimeFactors n)
Something went wrong with that request. Please try again.