Calculate the first largest factor of 600851475143

Question

ٍProblem description:

The prime factors of 13195 are 5, 7, 13 and 29. Largest prime factor 13195 is 29.

What is the largest prime factor of the number 600851475143 ?

Prime Factor:

any of the prime numbers that can be multiplied to give the original number.

Example:

Find the prime factors of 100:

100 ÷ 2 = 50; save 2

50 ÷ 2 = 25; save 2

25 ÷ 2 = 12.5, not evenly so divide by next highest number, 3

25 ÷ 3 = 8.333, not evenly so divide by next highest number, 4

But, 4 is a multiple of 2 so it has already been checked, so divide by next highest number, 5

25 ÷ 5 = 5; save 5

5 ÷ 5 = 1; save 5

List the resulting prime factors as a sequence of multiples, 2 x 2 x 5 x 5 or as factors with exponents, 2^2 x 5^2.

My Solution

This is my solution for problem 3 of Project Euler using Python:

def FLPF(n):
   '''Find Largest Prime Factor
   '''
   PrimeFactor = 1 
   i = 2

   while i <= n / i:
      if n % i == 0:
         PrimeFactor = i
         n /= i
      else:
         i += 1

   if PrimeFactor < n: PrimeFactor = int(n)

   return PrimeFactor

Answer 1

Couple of points:

• Use integer division, the double slash //. This has an update partner //= too so n //= i works as expected, and the result is always an integer.
• Multiplication is cleaner and perhaps a little clearer for your loop test, while i*i <= n:.
• As coded, the final value of n should be the largest prime factor of the passed parameter anyway - you don't actually need to keep PrimeFactor at all.
• It's good to make your function names and parameters reasonably descriptive. Python styles vary but you will often see underscore-separated phrases like def find_largest_prime_factor(target):. Of course this isn't so important for a small test routine for your own temporary use.
• You could perhaps speed things up in a couple of ways: by testing for factors of 2 first and then incrementing through the odd numbers, and by keeping a limit based on a square root which is only refreshed when a factor is found. Again not very important in this case.

def find_largest_prime_factor(target):

    remnant = target
    fac = 2
    while fac * fac <= remnant:
        if remnant % fac == 0:
            remnant //= fac
        else:
            fac += 1

    return remnant

Answer 2

• There is a style guide for Python you can consult.
• There is no use in trying to be creative when formatting the code, so you should write

_

if PrimeFactor < n: 
    PrimeFactor = int(n)

• Why do you convert n to an int(n) at the end of the calculation. If it is necessary (I don't think it is necessary) to convert it to an int then you should do it before you do the calculations.

• It is a good idea to write a triple quote docstring after the "def" statement of the function definition to describe the purpose of the function. But you should also descript the parameters of the function and the result, e.g.

_

def FLPF(n):
    '''Find Largest Prime Factor
    input:
        n: an integer
        returns the largest prime factor of n
    '''

• such a docstring can be retrieved as the __doc__ property of the function object. There are tools that generate documentation of a Python module using these docstrings.

• FLPF: one should avoid such cryptic abbreviation, consult the style guide.

Function names should be lowercase, with words separated by underscores as necessary to improve readability.

• You should try to avoid floating point arithmetic, them you do not have to bother with rounding errors, so use // instead of /.

• You can try to speed up your algorithm so that you can factor larger integers. In this answer the author already proposed to skip the even factors. This reduces the number of iterations by a factor of 2. But actually the prime numbers are of the pattern 6*n+1 or 6*n-1. So you can reduce the number of iterations by a factor of 3.

• You can further avoid the division in the while loop after each iteration. Replace

  while i <= n / i:

by

while i <= r:

where r is the square root of n.

• in one of your previous questions in one of the answers the author wrote

Don't obsess over performance until you know you have a problem.

This is usually true, but not for Project Euler Problems. So you should fetch the time before the start and after the end of you calculation and show the time needed for your calculation. You can do it in the way as you did here. You can increase the length of your input until the calculations took too long, e.g. more than one minute. And you can try to estimate and measure the effect of your performance improvements