Algorithm recommendation for calculating prime factors (Python Beginner)

Question

SPOILER ALERT! THIS MAY INFLUENCE YOUR ANSWER TO PROJECT EULER #3

I managed to get a working piece of code but it takes forever to compute the solution because of the large number I am analyzing.

I guess brute force is not the right way...

Any help in making this code more efficient?

# What is the largest prime factor of the number 600851475143

# Set variables
number = 600851475143
primeList = []
primeFactorList = []

# 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:
        primeList.append(x)

# Iterate over primeList to check for prime factors of 'number'
for i in primeList:
    if number % i == 0:
        primeFactorList.append(i)

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

Answer 1

I'll first just address some basic problems in the particular algorithm you attempted:

You don't need to pre-generate the primes. Generate them on the fly as you need them - and you'll also see that you were generating way more primes than you need (you only need to try the primes up to sqrt(600851475143))

# What is the largest prime factor of the number 600851475143

# Set variables
number = 600851475143
primeList = []
primeFactorList = []

def primeList():
    # 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

# Iterate over primeList to check for prime factors of 'number'
for i in primeList():
    if i > number**0.5:
        break
    if number % i == 0:
        primeFactorList.append(i)

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

By using a generator (see the yield?) PrimeList() could even just return prime numbers forever by changing it to:

def primeList():
    x = 2
    while True:
        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
        x += 1

Although I can't help but optimize it slightly to skip over even numbers greater than 2:

def primeList():
    yield 2
    x = 3
    while True:
        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
        x += 2

If you abandon your initial idea of enumerating the primes and trying them one at a time against number, there is an alternative: Instead deal directly with number and factor it out -- i.e., doing what botengboteng suggests and breaking down the number directly.

This will be much faster because we're now checking far fewer numbers:

number = 600851475143                                                           

def factors(num):                                                               
    factors = []                                                                
    if num % 2 == 0:                                                            
        factors.append(2)                                                       
    while num % 2 == 0:                                                         
        num = num // 2                                                          
    for f in range(3, int(num**0.5)+1, 2):                                      
        if num % f == 0:                                                        
            factors.append(f)                                                   
        while num % f == 0:                                                     
            num = num // f
         # Don't keep going if we're dividing by potential factors               
         # bigger than what is left.                                             
         if f > num:
            break                                                      
    if num > 1:                                                                 
        factors.append(num)                                                     
    return factors                                                              

# grab last factor for maximum.                                                                                
print(factors(number)[-1])

Answer 2

I made this code, everything is explained if you have questions feel free to comment it

def max_prime_divisor_of(n):
    for p in range(2, n+1)[::-1]: #We try to find the max prime who divides it, so start descending
        if n%p is not 0: #If it doesn't divide it does not matter if its prime, so skip it
            continue
        for i in range(3, int(p**0.5)+1, 2): #Iterate over odd numbers
            if p%i is 0:
                break #If is not prime, skip it
            if p%2 is 0: #If its multiple of 2, skip it
                break
        else: #If it didn't break it, is prime and divide our number, we got it
            return p #return it
        continue #If it broke, means is not prime, instead is just a non-prime divisor, skip it

If you don't know: What it does in range(2, n+1)[::-1] is the same as reversed(range(2, n+1)) so it means that instead of starting with 2, it starts with n because we are searching the max prime. (Basically it reverses the list to start that way)

---

Edit 1: This code runs faster the more divisor it has, otherwise is incredibly slow, for general purposes use the code above

def max_prime_divisor_of(n): #Decompose by its divisor
    while True:
        try:
            n = next(n//p for p in range(2, n) if n%p is 0) #Decompose with the first divisor that we find and repeat
        except StopIteration: #If the number doesn't have a divisor different from itself and 1, means its prime
            return n

If you don't know: What it does in next(n//p for p in range(2, n) if n%p is 0) is that gets the first number who is divisor of n

Answer 3

First calculate the sqrt of your number as you've done.

number = 600851475143
number_sqrt = (number**0.5)+1

Then in your outermost loop only search for the prime numbers with a value less than the sqrt root of your number. You will not need any prime number greater than that. (You can infer any greater based on your list).

for x in range(2, number_sqrt+1):

To infer the greatest factor just divide your number by the items in the factor list including any combinations between them and determine if the resultant is or is not a prime.

No need to recalculate your list of prime numbers. But do define a function for determining if a number is prime or not.

I hope I was clear. Good Luck. Very interesting question.

Answer 4

You can use user defined function such as

def isprime(n):
if n < 2:
    return False
for i in range(2,(n**0.5)+1):
    if n % i == 0:
        return False

return True

it will return boolean values. You can use this function for verifying prime factors.

OR

you can continuously divide the number by 2 first

n = 600851475143
while n % 2 == 0:
    print(2),
    n = n / 2

n has to be odd now skip 2 in for loop, then print every divisor

for i in range(3,n**0.5+1,2):
    while n % i== 0:
        print(i)
        n = n / i

at this point, n will be equal to 1 UNLESS n is a prime. So

if n > 1:
    print(n)

to print itself as the prime factor.

Have fun exploring