[Haskell-beginners] Integer factorization
David Frey
dpfrey at shaw.ca
Wed Mar 11 15:55:50 EDT 2009
On 3/10/2009, "Sergey V. Mikhanov" <sergey at mikhanov.com> 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
This is my solution to the same problem. I'm just a beginner with
Haskell as well, so just consider this as an alternate solution, not an
ideal solution.
The bottom 2 functions were pulled out of support code that I use for all
my Project Euler solutions, so that's why they seem unnecessarily
generic.
I think the only real advantages of my solution over yours is that I take
advantage of the fact that primes are always odd (except for the number
2) and that the largest prime factor of a number will always be <= half
its value.
main = putStrLn output
output = show result
result = largestPrimeFactor 600851475143
largestPrimeFactor n = last $ primeFactors n
{-
- Gets the prime factors of an integer.
-}
primeFactors :: (Integral a) => a -> [a]
primeFactors n = primeFactorsUsingPrimesList (2:[3, 5 .. n `div` 2]) n
{-
- Gets the prime factors of a number. The primes list passed as the
first
- argument is not required to be a list of primes. It is simply
required to be
- a list of values to try to divide the input from. If this list
contains
- non-prime values, they should be ordered. If the list does not
contain all
- of the primes that are divisors of the input value, then the result
will be
- incorrect.
-}
primeFactorsUsingPrimesList :: (Integral a) => [a] -> a -> [a]
primeFactorsUsingPrimesList _ 1 = []
primeFactorsUsingPrimesList (x:xs) n = if n `rem` x == 0
then x : primeFactorsUsingPrimesList (x:xs) (n `div` x)
else primeFactorsUsingPrimesList xs n
primeFactorsUsingPrimesList [] n = [n]
More information about the Beginners
mailing list