Finding all factors and prime factors of a number

Question

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

Answer 1

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