martedì 7 settembre 2010

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

import Data.List

solution = head $ reverse $ factors 600851475143

factors :: Integral a => a -> [a]
factors x = unfoldr nextFactor (x, primes)
    where nextFactor (1, _) = Nothing
          nextFactor (x, p:ps)
            | mod x p == 0 = Just (p, (divAll x p, ps))
            | otherwise = nextFactor (x, ps)
          divAll x factor
            | mod x factor == 0 = divAll (div x factor) factor
            | otherwise = x

primes :: Integral a => [a]
primes = 2 : iterate nextPrime 3
    where nextPrime x = head $ filter isPrime[(x+1)..] 

isPrime :: Integral a => a -> Bool
isPrime x = and $ [mod x p /= 0 | p <- takeWhile lowerThanSqrtX primes]
    where lowerThanSqrtX candidate = candidate <= (round $ sqrt $ fromIntegral x)




To be improved in the future...

Nessun commento:

Posta un commento