[Haskell-beginners] Integer factorization

[David Frey]

On 3/10/2009, "Sergey V. Mikhanov" <sergey at mikhanov.com> wrote:

>   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




This is my solution to the same problem.  I'm just a beginner with
Haskell as well, so just consider this as an alternate solution, not an
ideal solution.

The bottom 2 functions were pulled out of support code that I use for all
my Project Euler solutions, so that's why they seem unnecessarily
generic.

I think the only real advantages of my solution over yours is that I take
advantage of the fact that primes are always odd (except for the number
2) and that the largest prime factor of a number will always be <= half
its value.


main = putStrLn output
output = show result

result = largestPrimeFactor 600851475143


largestPrimeFactor n = last $ primeFactors n

{-
 - Gets the prime factors of an integer.
 -}
primeFactors :: (Integral a) => a -> [a]
primeFactors n = primeFactorsUsingPrimesList (2:[3, 5 .. n `div` 2]) n


{-
 - Gets the prime factors of a number.  The primes list passed as the
first
 - argument is not required to be a list of primes.  It is simply
required to be
 - a list of values to try to divide the input from.  If this list
contains
 - non-prime values, they should be ordered.  If the list does not
contain all
 - of the primes that are divisors of the input value, then the result
will be
 - incorrect.
 -}
primeFactorsUsingPrimesList :: (Integral a) => [a] -> a -> [a]
primeFactorsUsingPrimesList _      1 = []
primeFactorsUsingPrimesList (x:xs) n = if n `rem` x == 0
     then x : primeFactorsUsingPrimesList (x:xs) (n `div` x)
     else primeFactorsUsingPrimesList xs n
primeFactorsUsingPrimesList []     n = [n]