Project Euler Q3 Python Very Slow

Question

I'm a complete beginner in coding , So I thought I can get better by solving Project Euler Problems, I was stuck on question 3.

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

My code works on the smaller number example, however when I try the larger one it takes forever to run, how can I make my code more efficient?

n=3 #factors
l=[]
flag = True
while(n<600851475143):
  a=3
  if (600851475143%n==0):
    while(a<n):
      if n%a!=0:
        a+=2
      else:
        flag = False
        break
    if(flag):
      l.append(n)  

  n+=2 
print(l[len(l)-1])

If as you say you are new to coding then there are better ways of improving your skills than tackling the problems on Project Euler since many of those challenges involve insights into mathematics, optimisation or some other field, at least in my opinion. Better you should look for tutorials or exercises that are, as far as possible, pure programming. Best of luck in any case! — Bill Bell, May 09 '17 at 15:16
Check out Big O specifically the Order of Common Functions section https://en.wikipedia.org/wiki/Big_O_notation — quantik, May 09 '17 at 15:21
Yeah, you have two `while` loops nested. It grows with the square of the input value. See if you can flatten your idea down to one while loop. — Arya McCarthy, May 09 '17 at 15:26

score 2 · Answer 1 · answered Sep 16 '17 at 21:39

There are a few things you could do to speed up this code. First of all is getting a little more acquainted with math and some properties of prime numbers.

Prime numbers

Integer factorization

Why do we check up to the square root of a prime number to determine if it is prime or not

The other thing is (at least for me), your code is really hard to read... Try letting your intentions be more clear.

I tried to come up with a solution in python and it ran in 0.15s on my computer.

#!/usr/bin/env python
import math

def square_root_as_int(x):
  return int(math.sqrt(x))

def is_prime(number):
  if number == 1:
    return False
  for x in range(2, square_root_as_int(number) + 1):
    if x == number:
      next
    if number % x == 0:
      return False
  return True

def factors_of_(number):
  factors = []
  for x in range(2, square_root_as_int(number) + 1):
    if number % x == 0:
      factors.append(x)
      factors.append(number/x)
  return factors

factors = factors_of_(600851475143)
primes = []
for factor in factors:
  if is_prime(factor):
    primes.append(factor)
print max(primes)

# Bonus: "functional way"
print max(filter(lambda x: is_prime(x), factors_of_(600851475143)))

score 0 · Answer 2 · answered Jan 11 '18 at 16:59

You can also use generators, that worked for me.

Here is an example:

# Set variables
number = 600851475143
primeFactorList = []

def primeList(number):
    # Make list of prime numbers < 'number'
    for x in range(2, number+1):
        isPrime = True
        # Don't calculate for more than the sqrt of number for efficiency
        for y in range(2, int(x**0.5)+1):
            if x % y == 0:
                isPrime = False
                break
        if isPrime:
            yield x

# Calculate  primes using primeList and check for prime factors of 'number'
for i in primeList(number):
    if i > number**0.5:
        break
    if number % i == 0:
        primeFactorList.append(i)

# Print largest prime factor of 'number'
print(max(primeFactorList))

Project Euler Q3 Python Very Slow

2 Answers2