Project Euler problem #3

Question

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))

• JaDogg: Hello, welcome to CR. Could you please format the question properly?
• JaDogg: See codereview.stackexchange.com/help/formatting
• Graipher: Please add the problem description as text. Although Project Euler has been around for quite some time, it might not be around forever.

Answer 1

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))