Project Euler #3 - how inefficient is my code?

Question

So I am essentially a complete newbie to programming, and have been attempting to learn Python by completing the Project Euler problems. I haven't gotten very far, and this is my code for problem #3 :

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

Although my solution works, I'd like to know how I can improve.

primes = [2]
factors = []

def isPrime(x):
    a = 1
    if x == 1:
        return False
    while a < x:
        a += 1
        if x % a == 0 and a != x and a != 1:
            return False
            break
    return True

def generatePrime():
    a = primes[-1]+1
    while isPrime(a) == False:
        a += 1
    primes.append(a)

def primeFactor(x):
    a = primes[-1]
    while a <= x:
        if x % a == 0:
            factors.append(a)
            x /= a
        generatePrime()
        a = primes[-1]

primeFactor(input("Enter the number: "))
print("The prime factors are: " + str(factors) + "\nThe largest prime factor is: " + str(sorted(factors)[-1]))

Answer 1

You can save quite a bit time on your prime generation. What you should keep in mind is that a prime is a number which is no multiple of a prime itself; all other numbers are.

So in your isPrime function you can just go through your primes list and check if each prime is a divisor of the number. If not, then it is a prime itself. Of course you would need to make sure that you fill your primes list enough first.

As the most basic idea, you only need to check until sqrt(n), so you only generate numbers this far. And you can also just skip every even number directly. You could also make similar assumptions for numbers dividable by 3 etc., but the even/uneven is the simplest one and enough to get fast results for not too big numbers.

So a prime generation algorithm, for possible prime divisors up to n, could look like this:

primes = [2]
for i in range(3, int(math.sqrt(n)), 2):
    isPrime = not any(i % p == 0 for p in primes)
    if isPrime:
        primes.append(i)

Then to get the prime factors of n, you just need to check those computed primes:

primeFactors = []
m = n
for p in primes:
    while m % p == 0:
        m = m / p
        primeFactors.append(p)
    if m == 0:
        break

print('The prime factorization of `{0}` is: {1}'.format(n, '×'.join(map(str,primeFactors))))

For the euler problem 3 with n = 317584931803, this would produce the following output:

The prime factorization of 317584931803 is: 67×829×1459×3919

Answer 2

My code takes 2 milliseconds to execute from tip to tail ...

# 600851475143

import math

import time

number = int(input("> "))

start_time = time.time()


def prime_factors(number):

    prime_factorization = []

    box = number

    while number > 1:
        for i in range(math.floor(math.log2(number))):
            for j in range(2, number + 1):
                if number % j == 0:
                    prime_factorization.append(j)
                    number = number//j
                    last_factor = j
                    if last_factor > math.sqrt(box):
                        return prime_factorization
                    break
    return prime_factorization


print(f"Prime factors = {prime_factors(number)}")

print(f"execution time = {time.time() - start_time} seconds")