[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