CODEWITHSUNDEEP
pythonmathmathematical-optimization
Konstantin Dinev
Konstantin Dinev

Reputation: 34895

Finding all divisors of a number optimization

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.

Upvotes: 3

Views: 21986

Answers (4)

Ben Ruijl
Ben Ruijl

Reputation: 5123

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.

Upvotes: 25

MikeFHay
MikeFHay

Reputation: 9003

I don't know if there's much of a performance hit, but I'm pretty sure that cast to an int is unnecessary. At least in Python 2.7, int x / int y returns an int.

Upvotes: 0

MatthieuW
MatthieuW

Reputation: 2372

I would do a prime factor decomposition, and then compute all divisors from that result.

Upvotes: 1

raina77ow
raina77ow

Reputation: 106385

I'd suggest storing the result of math.sqrt(x) in a separate variable, then checking y against it. Otherwise it will be re-calculated at each step of while, and math.sqrt is definitely not a light-weight operation.

Upvotes: 3

Related Questions