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

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