Project Euler problem #3

My code works but would take 160 days to run lol.

#prime factors - ex.3

primes = []
for possibleprime in range (2,100000,1):
isPrime = True
for num in range(2, possibleprime, 1):
if possibleprime % num == 0:
isPrime = False

if isPrime:
primes.append(possibleprime)

#print(primes)

def prime(n):
prime_factors = []
n = int(n)
for x in primes:
if n % x == 0:
prime_factors.append(x)
return prime_factors

# n = 13195
# print(prime(n))

n = 600851475143
print(prime(n))

• Hello, welcome to CR. Could you please format the question properly? Feb 28 '19 at 16:35
• Feb 28 '19 at 16:50
• Please add the problem description as text. Although Project Euler has been around for quite some time, it might not be around forever. Feb 28 '19 at 17:21

1 Answer

The way you generate primes is very inefficient. There are a few quick fixes to speed it up. But first let's put the primality check into its own function:

def is_prime(n):
prime = True
for num in range(2, n):
if n % num == 0:
prime = False
return prime

primes = [n for n in range(2, 100000) if is_prime(n)]


This uses a list comprehension, the fact that the default increment of range is 1 and follows Python's official style-guide, PEP8.

Now, if you know that a number is composite, there is no need to check for all other numbers if they divide the number:

def is_prime(n):
for num in range(2, n):
if n % num == 0:
return False
return True


All prime numbers except for 2 are odd. So just start with 2 in the list and increment by 2:

    primes = [2] + [n for n in range(3, 100000, 2) if is_prime(n)]


You could even hard-code all primes below 10, but the performance gain from that is very small.

And finally, if you know that k is a divisor of n, then so is n // k. In other words, as soon as you have checked all values smaller than sqrt(n), you have already checked all possible divisors.

from math import sqrt

def is_prime(n):
for num in range(2, int(sqrt(n)) + 1):
if n % num == 0:
return False
return True


There are even faster ways to generate all primes up to some number and they are known as sieves (since they sieve out multiples of numbers for which you know that they are prime). One possible implementation as a generator of the well-known Sieve of Eratosthenes is this:

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

primes = list(prime_sieve(100000))