# Finding all factors and prime factors of a number

I am working on the Project Euler, number 3 project (finding the largest prime factor of 600851475143), but I wanted to take it a step further and write something that will list all factors and prime factors of any inputted number. I'm also using this project to learn about classes (I'm putting all my different Proj. Euler challanges in their own class). Anyway, I know my code works, but when i put in the number they wanted me to use -- 600851475143 --, it sat for over five minutes and hadn't finished yet. Is there a way to optimize my code to work more efficiently?

challangesEuler.py

class ChallangeThree:
"""Challange Three: Find the largest prime factor of 600,851,475,143

>> Takes a number, and finds it's prime factor. From there figures out
which is the largest"""

def __init__(self, value):  # Defines variables
self.val = value
self.dividend = 2
# self.maxfactor = math.sqrt(value)... NOT USED
self.listdivids = []
self.listprimes = []

def isprime(self, val):  # Called by 'findprimes' after getting all factors
for factor in range(2, val):
if val % factor == 0:
break  # If not prime, stop trying
else:
self.listprimes.append(val) # Add new prime to list

def factor(self):  # Called by 'findprimes' to find all factors
while self.val / self.dividend != 1:
if self.val % self.dividend == 0:
self.listdivids.append(self.dividend)
pass
else:
pass
self.dividend += 1
continue
self.listdivids.sort()
return self.listdivids  # Returns list of dividends

def findprimes(self): # The part called in execution module
self.factor()  # Finds factors
print(self.listdivids)  # Prints list of factors
for dividend in self.listdivids:  # For each dividend in the list, see if it's a factor
self.isprime(dividend)  # Runs each dividend through the code
return self.listprimes  # Returns list of prime factors


runEuler.py


import challangesEuler as Pr

def challangethree(x):  # Creates a function to run challange three in other
ct = Pr.ChallangeThree(x)
return ct.findprimes()

print(challangethree(600851475143))


## 1 Answer

Correct me if I am wrong but I think your code in findprimes is checking every number to see if it is a factor and then checking every factor to see if it is prime.

Rather than doing this I suggest you want to find all the prime factors, and then making the list of all factors just comes from all the combinations of prime factors in two subsets.

When you look for the prime factors of a number you can save yourself some time buy only checking odd numbers (and 2) up to the square root of the number. Whenever you find a new prime factor reduce you target by that factor. There are more advanced algorithms that you may want to explore here

In terms of coding style you might want to change your inline comments to doc strings, remove double new lines between functions and add hyphens to your function names e.g findprimes >> find_primes

In terms of function names I would have expected isprime to return True or False if the number was or wasn't prime.

I've made a quick sketch of the method I am describing:

import math

def find_prime_factors(target, floor=2):
prime_factors = []

while floor == 2 and target % 2 == 0:
target = target // 2
prime_factors.append(2)

candidate = floor + 1 if floor == 2 else floor

while candidate <= target:
while target % candidate == 0:
target = target // candidate
prime_factors.append(candidate)
candidate += 2
return prime_factors

• Thank you for all the feedback!! Your method does work better than mine, so thats really useful, and it uses a some neat things I hadn't seen before too! Thx! As for styling, I'll definitely keep it in mind, the double line breaks were put in place by PyCharm, but everything else definitely makes sense! – Zach Frost Jun 17 '20 at 22:37
• Curious why you use so many while statements? for the target % candidate couldn't you use an if statement and just add else: pass since the candidate <= target will already continue iterating? – Zach Frost Jun 17 '20 at 22:57