Christian Maeder Christian.Maeder at dfki.de
Tue Mar 10 13:24:31 EDT 2009

```On

"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
```