Project Euler Problem #3

While Problem #2 of Project Euler may have featured the very common Fibonacci numbers, Problem #3 is the first to feature the super common prime numbers. Here is the statement of Problem #3:

Project Euler Problem 3: Largest Prime Factor
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Factoring large numbers is a very common part of solving Project Euler problems. When the numbers are too large, it can be difficult to check every possible number as a possible divisor. Luckily, there is a trick we can use to determine if a number is prime as soon as possible.

Solution #1: Factors Less Than or Equal to the Square Root

The trick we can notice is that any composite number n can be written as the product of 2 factors a and b such that both a and b are greater than 1. If both a and b were greater than the square root of n, then it would be impossible for their product to be equal to n. Thus, any composite number must have at least one proper factor which is less than or equal to its square root. Consequently, any number which does not have a proper factor less than or equal to its square root must be prime. This fact will probably be used in many Project Euler problems, so I will only explain it in this post.

Using this trick, it is easy to find any small prime factors of a large composite number. However, this question has asked for the largest prime factor of a large number. To get around this problem, one method we can use is dividing out any prime factors we find until the value we’re left with is prime. By default, the resulting number would have to be the largest prime. This method can be made more efficient by the trick above, as the number of potential factors decreases every time a prime is divided out.

Here is an implementation of this method in Python 2.7:

'''
 Author: Walker Kroubalkian
 "Dividing Out" Approach to Project Euler Problem #3
 '''

 import time
 from math import sqrt

 def projectEulerProblemThree(n):
     c = 2
     while(c<=sqrt(n)):
         if(n%c==0):
             while(n%c==0):
                 n/=c
         c+=1

     if(n==1):
         return (c-1)

     return n

 start = time.time()
 print projectEulerProblemThree(600851475143)
 print("--- %s seconds ---" % (time.time() - start))

 '''
 Prints
 6857
 --- 0.00019097328186 seconds ---
 for input of n = 600851475143
 '''

Factoring and primes are extremely important parts of mathematics, and as a result, I will probably refer back to the facts discussed in this post in future posts.

Signing off for today. Thanks for reading!