On 3/10/2009, "Sergey V. Mikhanov"
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]