euler/haskell/e003.hs

27 lines
770 B
Haskell
Raw Permalink Normal View History

2011-10-11 04:39:50 +00:00
{-
Find the largest prime factor of a composite number.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
-}
import Text.Printf
pfactor :: (Integral a) => a -> [a]
2011-10-11 17:02:51 +00:00
pfactor n = pfactor_ n [] 2
2011-10-11 04:39:50 +00:00
2011-10-11 17:02:51 +00:00
pfactor_ n factors start =
let next = pfactor_next n start in
if n == next
then n:factors
else pfactor_ (n `div` next) (next:factors) next
2011-10-11 04:39:50 +00:00
pfactor_next :: (Integral a) => a -> a -> a
2011-10-11 17:02:51 +00:00
pfactor_next n last
| n <= last = n
| otherwise = head (filter (\x -> n `rem` x == 0 || n == x) [last..n])
2011-10-11 04:39:50 +00:00
main = do
2011-10-11 17:02:51 +00:00
printf "Largest prime factor of 13195: %d\n" (head (pfactor 13195) :: Integer)
printf "Largest prime factor of 600851475143: %d\n" (head (pfactor 600851475143) :: Integer)