1

I'm having a go at project Euler Q3 and need to get the largest prime factor of a number. So far I've gotten a pair of functions to return a list of all the factors of the given number but it seems like a really bad way to do it (partly because I only need the largest).

get_factors :: (Integral a) => a -> [a] -> [a]
get_factors _ [] = []
get_factors t (x:xs)
    | t `mod` x == 0 = x:get_factors t xs
    | otherwise = get_factors t xs

factors :: (Integral a) => a -> [a]
factors x = get_factors x [x,x-1..1]

> factors 1000
> [1000,500,250,200,125,100,50,40,25,20,10,8,5,4,2,1]

It seems weird to me that I would need to have a "launch" function if you will to start the recursive function off (or have a function where I have to pass it the same value twice, again, seems silly to me).

Can you point me in the right direction of how I should be going about doing this please?

hammar
  • 138,522
  • 17
  • 304
  • 385
Teifion
  • 108,121
  • 75
  • 161
  • 195
  • 2
    I just want to point out that if `y` is the smallest prime factor of `x`, then `x \`div\` y` is the largest one. You may be able to save some computation here. If you use a [fast implementation of the Eratosthenes' sieve](http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29) instead of the linear trial divisors list, you may be able to save some more. – n. m. could be an AI May 05 '13 at 17:34
  • 1
    @n.m. ```x `div` y``` need not be prime. – hammar May 05 '13 at 17:36
  • 1
    @hammar Yes, just realized that after hitting enter... OTOH the presented procedure does not produce prime factors either. – n. m. could be an AI May 05 '13 at 17:37
  • I figured I'd create factors first then filter them based on primeness. I wanted to break the problem down. – Teifion May 05 '13 at 18:04

3 Answers3

8

You should try to recognize that what you're doing here, namely picking elements from a list which satisfy some condition, is a very common pattern. This pattern is implemented by the filter function in the Prelude.

Using filter, you can write your function as:

factors n = filter (\d -> n `mod` d == 0) [n, n-1 .. 1]

or, equivalently, you can use a list comprehension:

factors n = [d | d <- [n, n-1 .. 1], n `mod` d == 0]
hammar
  • 138,522
  • 17
  • 304
  • 385
4

Using a "launch" function for calling a recursive function is very common in Haskell, so don't be afraid of that. Most often it'd be written as

f = g someArgument
  where
    g = ...

in your case

factors :: (Integral a) => a -> [a]
factors x = get_factors [x,x-1..1]
  where
    get_factors [] = []
    get_factors (y:ys)
        | x `mod` y == 0   = y : get_factors ys
        | otherwise        = get_factors ys

This signals readers of your code that get_factors is used only here and nowhere else, and helps you to keep the code clean. Also get_factors has access to x, which simplifies the design.

Some other ideas:

  • It's inefficient to try dividing by all numbers. In problems like that it's much better to pre-compute the list of primes and factor using the list. There are many methods how to compute such a list, but for educational purposes I'd suggest you to write your own (this will come in handy for other Project Euler problems). Then you could take the list of primes, take a part of primes less or equal than x and try dividing by them.
  • When searching just for the largest factor, you have to search through all primes between 1 and x. But if x is composite, one of its factors must be <= sqrt(n). You can use this to construct a significantly better algorithm.
Petr
  • 62,528
  • 13
  • 153
  • 317
2

I do not think it is a very good idea to go through every number like [n, n-1..] since the problem says 600851475143. 

largest_factors :: Integer -> Integer
largest_factors n = helper n 2
    where
        helper m p  
            | m < p^2 = m
            | m == p = m
            | m `mod` p == 0 = helper (m `div` p) p
            | otherwise = helper m (p+1)

What I did is that, once it found that a certain number, say p, divides the number n, it just divides it. This one works on my computer just fine. This gave me the solution within a sec.

Tengu
  • 1,014
  • 7
  • 14
  • This works well in this case because the input number happens to have low prime factors. One simple improvement you can make is that once `p*p > m`, `m` must be prime, so you can stop there instead of continuing all the way to `m == p`. – hammar May 05 '13 at 20:34