Euler problem 3: largest prime factor of the number

Question

I have been trying to learn Python and just solved Euler Problem 3:

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

What is the largest prime factor of the number 600851475143 ?

I am looking for any feedback on improving efficiency and the code itself.

My code:

from itertools import count, islice
def is_prime(number):
 for n in islice(count(2), int(number**0.5 -1)):
 if number % n == 0:
 return False
 return True
def find_factors(number):
 lst = []
 for n in islice(count(2), int(number/2-1)):
 if number % n == 0:
 if is_prime(n):
 lst.append(n)
 return lst
print(find_factors(13195).pop())

I used islice instead of xrange because of int limits, which I learned about from another question at StackOverflow.com

In code above, I have created two separate functions, one to find a prime and the other to find factors.

The program works this way,

• It takes an input number
• Find all the factors of that number from 2->number/2
• If it finds a factor, it checks if its a prime, and append it to a list.
• Eventually I print the last element of list since list in python are ordered.

• Martin R: There are far more efficient methods to get the result. I suggest to have a look at other Q&A's about the same problem.
• MaverickD: Thank you for your response Martin. I have already seen other solution. My goal is to not solve the problem, my goal is to learn to code more efficiently and find where i lack. Of course, I can just follow what others did. But I want to learn how can I improve my own code. After that I will definitely follow other efficient solutions. I hope this makes sense.
• 200_success: If you're talking about Python 3.x, there is no xrange() — that's only in Python 2.x.
• 200_success: Technically, you haven't really solved Project Euler Problem 3, since you've just demonstrated the given example of 13195. Your algorithm is much too inefficient to work for 600851475143. You really could benefit from looking at other answers about the same problem.

Answer 1

When I look at your solution, the first impression I get is that it's too complicated. To solve the problem you don't need any fancy algorithms for prime numbers, or islice and count. It's a simple task of trying to divide by possible factors.

One important thing to note is that we only need to check for prime factors that are smaller than the square root of the number. Once we have reached the square root, there can be only one remaining factor, which can be proved by contradiction.

Another important thing to note is that once we have found a prime factor, we can divide the original number by that factor and reduce our problem size.

Doing both of these things, I end up with something like this:

def get_max_prime_factor(n):
 d = 2
 factors = []
 while d*d <= n:
 while n%d == 0:
 n //= d
 factors.append(d)
 d += 1
 if n != 1:
 factors.append(n)
 return max(factors)

Now, I'll say that even this implementation might be too complicated, since I'm saving all prime factors in a list instead of only keeping track of the largest one. If you want you could change that implementation and make it even more efficient, but to solve the problem above it's not necessary.

• maxb: @TobySpeight Good catch, I'll change it.

Answer 2

Another, slightly slower, approach, but which helps you in future Project Euler problems, is using the same algorithm as in the answer by @maxb, but instead of dividing by every number, only divide by the primes up to \$\sqrt{n}\$. For this you can use a prime sieve (a fast method to get all primes up to some number):

def prime_sieve(limit):
 prime = [True] * limit
 prime[0] = prime[1] = False
 for i, is_prime in enumerate(prime):
 if is_prime:
 yield i
 for n in range(i * i, limit, i):
 prime[n] = False
def prime_factors(n):
 for p in prime_sieve(int(n ** 0.5) + 1):
 while n % p == 0:
 n //= p
 yield p
 if n != 1:
 yield n
if __name__ == "__main__":
 for n in (13195, 600851475143):
 print(n, max(prime_factors(n)))

Here I used a basic implementation of the sieve of Eratosthenes in pure Python. Faster implementations exist.

Some speed comparisons:

%timeit max(prime_factors(13195))
19.2 μs ± 771 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit get_max_prime_factor(13195)
3.55 μs ± 68.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit find_factors(13195).pop()
873 μs ± 217 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

And for the actual number in the problem:

%timeit max(prime_factors(600851475143))
120 ms ± 1.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit get_max_prime_factor(600851475143)
394 μs ± 6.68 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit find_factors(600851475143).pop()
running for more than 10 minutes...