[Haskell-beginners] Integer factorization

Sergey V. Mikhanov sergey at mikhanov.com
Mon Mar 9 21:21:35 EDT 2009


   Hello,

I am solving a problem of finding the largest prime factor of
600851475143 (Project Euler is great for learning new language!), and
came with the following solution (it uses the most ineffective
approach to finding prime numbers, however is able to factor the above
number in fraction of second):

factors :: Integer -> [Integer]

factors n = doFactors n (eratosthenesFilter [1..n])

doFactors n primes
    | null newPrimes = []
    | otherwise      =
        let topPrime = head newPrimes in
        if topPrime == n
            then [topPrime]
            else topPrime : (doFactors (n `quot` topPrime) primes)
    where
        newPrimes = snd $ break (\x -> (n `rem` x) == 0) primes

eratosthenesFilter :: [Integer] -> [Integer]

eratosthenesFilter [] = []
eratosthenesFilter (num : nums)
    | num == 1  = eratosthenesFilter nums
    | otherwise = num : (eratosthenesFilter $ doFilter num nums)
    where
        doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums

What would you do different (including stylistic changes)? What are
the general comments about efficiency (not of the algorithm, but of
the implementation: for example, is it fine to use break at every
invocation of doFactors?) and elegance of the solution?

Thanks and regards,
Sergey


More information about the Beginners mailing list