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