[Haskell-beginners] Re: Integer factorization

[Christian Maeder]

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