Project Euler #3 with Python

Question

I tried to solve some Euler's problems, this is the solution I found for problem #3 with Python. The problem asks:

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

How can I improve my code?

def get_largest_prime2(value):
 start = time.clock() #used to measure the execution time
 divisors = [] #this list will be filled with all number's divisors
 i = 1
 while value != 1: 
 while value%i == 0: #check if the value can be divided by i and, if so, iterate the process.
 value = (value // i)
 divisors.append(i)
 if i == 1 : break #it's needed to avoid an infinity loop
 if i >= 3: i += 2 #when i is bigger than 3, search divisors among odd numbers( this reduces the search field)
 else: i += 1 
 print( time.clock()-start)
 return max(divisors) #returns the max prime divisors

Answer 1

timing

Put the code to time the run time of the function outside of the function.

augmented assignment

value = (value // i) can be expressed as value //= i

divisors

Why do you need to keep a list of divisors? They only ask for the largest one. The largest one will always be the last one, so you just need to remember that.

pep-8

• Your variable names are clear and in the correct format, apart from i. I would rename that to divisor or prime.
• The spacing around the operators and ( is inconsistent.
• the if i >= 3: i += 2 on one line is advised against.

increments

 if i >= 3: i += 2 #when i is bigger than 3, search divisors among odd numbers( this reduces the search field)
 else: i += 1 

can be simplified to i += (2 if i >= 3 else 1) or even i += 1 + (i >= 3), using the fact that int(True) is 1. But here you don't use the fact that your divisors are all primes. A quicker process would be to get the next possible divisor from a prime generator, instead of incrementing by 2 manually.

while loop

You can integrate the if i == 1 : break into the condition for the while loop: while value % prime == 0 and value != 1:

---

def largest_prime_divisor(value):
 largest_divisor = 1
 for prime in prime_generator():
 while value % prime == 0 and value != 1:
 value //= prime 
 largest_divisor = prime 
 return largest_divisor

Possible implementations of prime_generator can be found in dozens of SO and Code review posts.

shortcut

If the divisor is larger than the square root of the value, you know the next divisor will be the value itself, so you can shortcut when the divisor exceeds this.

def largest_prime_divisor(value):
 largest_divisor = 1
 for prime in prime_generator():
 while value % prime == 0:
 value //= prime 
 largest_divisor = prime 
 if prime ** 2 > value:
 return max(largest_divisor, value)
 return largest_divisor

• Josiah: The special case check for i = 1 can equally be avoided by starting i as 2.

Answer 2

Supplement to Maarten Fabré's answer:

We don't even need to remember largest_divisor, as we can simply use value itself. When the current prime being considered is too large to be a factor of value, just return value:

def largest_prime_divisor(value):
 for prime in prime_generator():
 while value > prime and value % prime == 0:
 value //= prime
 if prime * prime > value:
 return value