Project Euler Problem 3

September 20, 2011

Problem 3 at Project Euler asks the reader to solve this problem:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Given the amount of factoring code on this website, I find that problem quite simple. But judging from Reddit and Stack Overflow, other programmers find the problem anything but simple. If you look at the dates, you will notice that the problem seems to come up every few months. And if you read the comments on Reddit and Stack Overflow, the saddest part is that a lot of the answers are wrong; in fact, some of them are mind-numbingly wrong. So I decided to write a canonical solution to the problem:

Project Euler Problem 3 asks for the largest prime factor of the number 600851475143. We consider first a function to find all the prime factors of any number. A simple way, not necessarily the best way but sufficient for this task and for many others, works in two steps: first remove factors of 2 while the number is even, then perform trial division by the odd numbers starting from 3 until the factorization is complete. Here’s a formal statement of the algorithm to find the factors of a given input number n:

1. Create a list of factors, initially empty.

2. If n is even, add 2 to the end of the list of factors, divide n by 2, and go to Step 2.

3. Set f ← 3.

4. Calculate the quotient q and remainder r when dividing n by f, so that n = q f + r with 0 ≤ r < f.

5. If r > 0, set ff + 2 and go to Step 4.

6. Otherwise, r = 0. Add f to the end of the list of factors. Set nq.

7. If n < f2, add n to the end of the list of factors, output the list of factors, and stop.

8. Otherwise, go to Step 4.

Consider as an example the factorization of 13195; it’s odd, so we pass Step 2 and go to Step 3 with f = 3. The quotient and remainder of 13195 ÷ 3 are 4398 and 1, so in Step 5 we set f = 3 + 2 = 5 and go to Step 4. The quotient and remainder of 13195 ÷ 5 are 2639 and 0, so in Step 6 we add 5 to the end of the list of factors, making the list {5}, and we set n = 2639. Then, in Step 7, we note that 2639 < 52 is false, so we go to Step 8 and then to Step 4. In Step 4 we calculate the quotient and remainder of 2639 ÷ 5 as 527 and 4, and since the remainder is greater than 0 we set f = 5 + 2 = 7 and go to Step 4. In Step 4 we calculate the quotient and remainder of 2639 ÷ 7 as 377 and 0, so in Step 6 we add 7 to the end of the list of factors, making the list {5, 7}, and we set n = 377. Then, in Step 7, we note that 377 < 72 is false, so we go to Step 8 and then to Step 4. In Step 4 we calcuate the quotient and remainder of 377 ÷ 7 as 53 and 6, and since the remainder is greater than 0 we set f = 7 + 2 = 9 and go to Step 4. In Step 4 we calculate the quotient and remainder of 377 ÷ 9 as 41 and 8, and since the remainder is greater than 0 we set f = 9 + 2 = 11 and go to Step 4. In Step 4 we calculate the quotient and remainder of 377 ÷ 11 as 34 and 3, and since the remainder is greater than 0 we set f = 11 + 2 = 13 and go to Step 4. In Step 4 we calculate the quotient and remainder of 377 ÷ 13 as 29 and 0, so in Step 6 we add 13 to the end of the list of factors, making the list {5, 7, 13}, and we set n = 29. Then, in Step 7, we note 29 < 132, so we add 29 to the end of the list of factors, making the list {5, 7, 13, 29}, output the list of factors, and stop. Thus, the complete factorization is 13195 = 5 × 7 × 13 × 29.

Given a function to find the prime factors of a number, the solution to Project Euler Problem 3 is easy: it’s just the last prime factor in the list, which is necessarily the largest prime factor in the list since we worked with increasing f and always added prime factors to the end of the list.

You may notice that the challenge number in the problem, 600851475143, is too large to represent using 32-bit arithmetic. That’s part of the Project Euler task — you need to find a library that allows you to do arithmetic on numbers longer than 32 bits. In fact, Project Euler uses this problem as kind of a gateway exercise, because many of the later problems also require arithmetic on integers longer than 32 bits. With C, the long long datatype is big enough, but you might need the gmp library for larger integers, with Java you probably want the BigInteger library, and with other languages you will need to find the corresponding library yourself, and let the compiler know where it is so it can be linked to your factoring code. Or you may prefer to use a language, such as Python or Lisp, that provides built-in support for integers longer than 32 bits.

If you want to know more about integer factorization, I humbly recommend the prime-number exercises at my blog.

Your task is to implement the function described above. If you solve the Project Euler problem, please publish only your code but not the solution, as we respect Project Euler’s request not to publish answers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

18 Responses to “Project Euler Problem 3”

  1. Graham said

    It looks like this may not behave well for powers of two, though it handles other evens fine:

    > (factors 2)
    (2 1)
    > (factors 4)
    (2 2 1)
    > (factors 8)
    (2 2 2 1)
    > (factors 10)
    (2 5)
    
  2. Graham said

    Python:

    def factors(n):
        fs = []
        while (n & 1 == 0):
            fs.append(2)
            n //= 2
        f = 3
        while n >= f * f:
            if (n % f == 0):
                fs.append(f)
                n //= f
            else:
                f += 1
        if n != 1:
            fs.append(n)
        return fs
    

    Huzzah for native big integers!

  3. programmingpraxis said

    How embarrassing! I need a step 2.5 that reads “If n = 1, output the list of factors and stop.” and make the corresponding change in the function.

  4. DGel said

    Trying to learn Google Go, first time using big.Int
    Have to say that I don’t find it very intuitive to use, but then again, I’m only just starting..


     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    func Factors(n *big.Int) (answer vector.Vector) {
    	var f, q, r, incr, zero, tmp big.Int
    	
    	f.SetInt64(2)
    	incr.SetInt64(2)
    	
    	for n.Bit(0) == 0 {
    		answer.Push(new(big.Int).Set(&f))
    		n.Div(n,&f)
    	}
    	f.SetInt64(3)
    	
    	for tmp.Mul(&f,&f).Cmp(n) < 1 {
    		q.DivMod(n, &f, &r)
    		
    		if r.Cmp(&zero) > 0 {
    			f.Add(&f, &incr)
    		} else {
    			n.Set(&q)
    			answer.Push(new(big.Int).Set(&f))
    		}
    	}
    	if n.Cmp(new(big.Int).SetInt64(1)) != 0 {
    		answer.Push(new(big.Int).Set(n))
    	}
    	return
    }
    

  5. DGel said

    Oh, sorry for the cruft.. used an online syntax highlighter, but doesn’t appear that it worked very well.

  6. slabounty said

    In ruby (pretty much exactly the same as Graham’s python version) …

    def prime_factors(n)
        fs = []
        while n % 2 == 0
            fs << 2
            n /= 2
        end
    
        f = 3
        while n >= f**2
            if n % f == 0
                fs << f
                n /= f
            else
                f += 1
            end
        end
        fs << n if n != 1
        fs
    end
    

    You could also monkey patch Integer to provide this in a more ruby like way.

  7. Phil said

    In Python. Slightly more verbose, and with the steps interspersed through the code as comments. I’m gradually getting the hang of Python.

    Source

  8. Mike said

    Here’s a slight twist on the described function. Rather than try all
    odd numbers >= 3, I used a 30-wheel to generate the possible factors.

    Also, the function is a generator which returns successive factors of its
    argument. Use list() to get the last factor.

    from itertools import accumulate, chain, cycle
    
    def genfactors(n):
        for f in accumulate(chain((2,1,2,2), cycle((4,2,4,2,4,6,2,6)))):
            if f*f > n:
                break
            
            while not n % f:
                yield f
                n //= f
                
        if n > 1:
            yield n
    
    #some tests
    print(list(genfactors(440190069936)))
    # -> [2, 2, 2, 2, 3, 317, 3803, 7607]
    
    

    @graham/@slabounty – I think line 12/14 should be f += 2, so that f skips even numbers.

  9. Graham said

    Thanks for catching that, @Mike; I could have sworn I put in += 2. Anyway, nice wheel! I’ll have to read up on wheel factorization and Python3’s accumulate.

  10. programmingpraxis said

    Graham, you can read about wheel factorization at the earlier exercise at Programming Praxis.

  11. Phil G said

    C# version

    	public class Euler3
    	{
    		public static long[] PrimeFactors(long n)
    		{
    //			1. Create a list of factors, initially empty.
    			var factors = new List<long>();
    
    //			2. If n is even, add 2 to the end of the list of factors, divide n by 2, and go to Step 2.
    			while( (n & 1) == 0)
    				n /= 2;
    
    //			3. Set f ← 3.
    			long f = 3;
    
    			while(true)
    			{
    //				4. Calculate the quotient q and remainder r when dividing n by f, so that n = q f + r with 0 ≤ r < f.
    				long q = n / f;
    				long r = n - q * f;
    				
    //				5. If r > 0, set f ← f + 2 and go to Step 4.
    				if ( r > 0 )
    				{
    					f += 2;
    				}
    				else
    				{
    //					6. Otherwise, r = 0. Add f to the end of the list of factors. Set n ← q.
    					factors.Add(f);
    					n = q;
    					
    //					7. If n < f2, add n to the end of the list of factors, output the list of factors, and stop.
    					if(n < f * f)
    					{
    						factors.Add(n);
    						break;
    					}
    				}
    			}
    			
    			return factors.ToArray();
    		}
    		
    		public static void Main(string[] args)
    		{
    			var x1 = 13195;
    			var fx1 = PrimeFactors(x1);
    			Console.WriteLine("Prime factors of '{0}' = [{1}]", x1, String.Join(", ", fx1));
    			
    			var x2 = 600851475143;
    			var fx2 = PrimeFactors(x2);
    			Console.WriteLine("Prime factors of '{0}' = [{1}]", x2, String.Join(", ", fx2));
    			Console.WriteLine("Largest prime factor = {0}", fx2[fx2.Length - 1]);
    			Console.ReadLine();
    		}
    	}
    
  12. Green said

    in c language

    #include
    int main()
    {
    long long int n = 600851475143;
    long long int a[100];
    long long int i,f,q,r,j;

    i=0;
    while(n%2==0)
    {
    a[i] = 2;
    i++;
    n=n/2;
    }
    f=3;
    while(n > (f*f))
    {
    q = n/f;
    r = n%f;
    if(r>0)
    {
    f = f+2;
    }
    else
    {
    a[i] = f;
    i++;
    n = q;
    if(n < (f*f))
    {
    a[i] = n;
    i++;
    }
    }
    }
    for(j=0; j<i; ++j)
    printf("%lld ",a[j]);
    printf("\n");
    return 0;
    }

  13. David said

    FORTH Version to find greatest prime factor. Rather than factor all even numbers, the first step factors all even numbers > 2. When n is equal to 2, the square test fails, so the odd factoring loop does not execute. Therefore there is no special case to check for n = 1 at the end, but more importantly the invariant is preserved that when the function ends, the greatest prime factor is on the stack as a 64 bit integer. (If the final “d.” and printing is removed, the FORTH word would become a function to return the largest prime factor.)

    : deven?  ( d -- ? )
        drop  1 and  0= ;
    
    : d/mod  ( d n -- d/n d%n )
         locals| n |
         \ FORTH does not have remainder function for double division
         \ so we multiply the quotient by the divisor and subtract...
         \
         2dup  1 n  M*/   2dup 2>r   \ get quotient & save a copy
         n 1 M*/ d- drop             \ compute remainder
         2r> ;                       \ restore quotient
    
    : .factors ( d -- )
        BEGIN 2dup deven? >r  2. 2over d<  r> and WHILE
            2 .  d2/
        REPEAT
    
        3 locals| f |
        BEGIN  2dup  f dup m*  d< not WHILE
            2dup f d/mod  rot 0= IF 
                f .
                2nip      \ drop n; quotient on stack replaces it
            ELSE
                2drop     \ drop quotient
                f 2 +  TO f
            THEN
        REPEAT
        d. ;
    

    Testing:

    13,195 .factors 5 7 13 29  ok
    1,472,991,001 .factors 23 359 178393  ok
    178393 359 m* 23 1 m*/ d. 1472991001  ok
    8, .factors 2 2 2  ok
    
  14. arkade said

    C#:
    long num = 600851475143;
    long f = 1;
    long z = 1;

    while (z != num)
    {
    if (num % f == 0)
    {
    Console.WriteLine(f);
    z = z * f;
    }
    f++;
    }
    Console.WriteLine(“DONE!”);
    Console.ReadLine();

  15. RandomlyGenerated said

    In Java:

    public class LargestPrimeFactor {
    private static double primefactor(double n) {
    double i=2;

    for(;itemp)? i:temp;

    }
    }

    return i;
    }

    public static void main(String[] args) {
    System.out.println(primefactor(600851475143.0));

    }

    }

  16. RandomlyGenerated said

    HMM the above code was cut off

    public class LargestPrimeFactor {

    private static double primefactor(double n) {
    double i=2;

    for(;itemp)? i:temp;

    }
    }

    return i;
    }

    public static void main(String[] args) {
    System.out.println(primefactor(600851475143.0));

    }

    }

  17. annie said

    I have done its very easy and convenient solution. Check this out here @ http://crispylogs.com/project-euler-problem-3-solution/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 644 other followers

%d bloggers like this: