CODEWITHSUNDEEP
pythonperformance
Angelrina
Angelrina

Reputation: 1

Project Euler Q3 Python Very Slow

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

Upvotes: 0

Views: 460

Answers (2)

Franco D&#39;Angelo
Franco D&#39;Angelo

Reputation: 135

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

Upvotes: 0

Frank Kair
Frank Kair

Reputation: 451

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

Upvotes: 2

Related Questions