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

• konijn: You should replace while a < x: with while a < math.sqrt(x): You can also check whether x is even and > 2, in that case it is not a prime, also google for 'prime sieve'.

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: ×ばつ3919

• Jaime: If you are not going to sieve to calculate your primes, you should at least bring together your prime calculation and factor testing together, so that as soon as you find the 67 factor, your largest prime to calculate is reduced from 563546 to 68848, and by the time you know 829 is a prime to 2391, and once 1459 is known as a prime you don't calculate any more primes to test as factors.
• poke: @Jaime Sure, you can again save a lot when combining those two. My original solution for problem 3 (which btw. doesn’t even require factorization) is a lot more concise too. But given OP’s original code structure I thought it would make more sense to show separated and reusable pieces. With my example I could once generate the primes and then just run the factorization against multiple numbers.

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

• Graipher: Hey, welcome to Code Review! Please add some more explanation on how and why your code is better (faster). Otherwise this is just an alternative solution, which alone is not enough for an answer here. Have a look at our help-center for more information.