[Haskell-beginners] Re: Integer factorization
Christian Maeder
Christian.Maeder at dfki.de
Tue Mar 10 13:24:31 EDT 2009
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
More information about the Beginners
mailing list