On http://www.haskell.org/haskellwiki/Prime_numbers "primeFactors" should do what you want (although I don't like the the pattern matching on "1") Cheers Christian Sergey V. Mikhanov 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