python - Finding all divisors of a number optimization

Question

I have written the following function which finds all divisors of a given natural number and returns them as a list:

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return divList

It works really well with the exception that it's really slow when the input is say an 18-digit number. Do you have any suggestions for how I can speed it up?

Update:

I have the following method to check for primality based on Fermat's Little Theorem:

def CheckIfProbablyPrime(x):
    return (2 << x - 2) % x == 1

This method is really efficient when checking a single number, however I'm not sure whether I should be using it to compile all primes up to a certain boundary.

Answer 1

You can find all the divisors of a number by calculating the prime factorization. Each divisor has to be a combination of the primes in the factorization.

If you have a list of primes, this is a simple way to get the factorization:

def factorize(n, primes):
    factors = []
    for p in primes:
        if p*p > n: break
        i = 0
        while n % p == 0:
            n //= p
            i+=1
        if i > 0:
            factors.append((p, i));
    if n > 1: factors.append((n, 1))

    return factors

This is called trial division. There are much more efficient methods to do this. See here for an overview.

Calculating the divisors is now pretty easy:

def divisors(factors):
    div = [1]
    for (p, r) in factors:
        div = [d * p**e for d in div for e in range(r + 1)]
    return div

The efficiency of calculating all the divisors depends on the algorithm to find the prime numbers (small overview here) and on the factorization algorithm. The latter is always slow for very large numbers and there's not much you can do about that.