Calculate the first largest factor of 600851475143

ٍ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


• 50 ÷ 2 = 25; save 2 2 was already saved, does it make sense to save it again?
– Mast
May 24 at 16:40
• why do you break the python format style in the second to last line and squeeze the two lines in ine line? May 24 at 17:46
• off topic: the first Project Euler exercises are rather simpel, but soon it will become rather difficulty and mathematically. And for most of the users very frustrating. So one should look for other sources of programming problems. One I found is the following: reddit.com/r/dailyprogrammer May 24 at 21:42

2 Answers

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

• 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

• "Don't obsess over performance until you know you have a problem" is true even for Project Euler. Moreover, measuring running time is mostly irrelevant for Euler-style problems, which often fall into two buckets: (1) current algorithm gets the job done fast enough (ie, no problem), or (2) need a more clever algorithm because the current approach is hopelessly slow (ie, no point in measuring it).
– FMc
May 24 at 22:57
• I would recommend using existing timing functions such as timeit(), rather than reinventing them from low-level parts. May 25 at 6:26
• @TobySpeight Using 'time' is not "reinventing" timing functions "from low-level parts" but it is the adequate way to measure the length of a time interval. But I do not speak of programs that run in a fraction of a second but from programs that run about a minute. Using the timeit function for the to measure the single run of such a program, with number=1, does not has any advantage. May 25 at 11:02