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.

Are you using the `CheckIfPrime` to see if you can skip divisions for a certain x? You should be careful with this, because you can get false positives: `CheckIfPrime` filters most numbers, but some composites still yield `True`! — Ben Ruijl, Sep 14 '12 at 10:24
@BenRuijl Can you please give me an example and thanks a lot! — Konstantin Dinev, Sep 14 '12 at 10:29
Your `CheckIfPrime` function doesn't work due to [Fermat pseudoprimes](http://en.wikipedia.org/wiki/Fermat_pseudoprime). For example, `CheckIfPrime(341)` is True, but 341 = 11*31. If `CheckIfPrime` is False, then the number is definitely composite, but the converse doesn't hold. [Ah, sorry, missed @BenRuijl's earlier comment to the same effect. I'll leave the example, though.] If you use it only as "CheckIfProbablyPrime", though, it could still be useful. — DSM, Sep 14 '12 at 10:32
@DSM Thanks a lot, I didn't consider the fact that it's not bidirectional (fermat's theorem). I will change it to CheckIfProbablyPrime. I will go with your approach. So in order to make it deterministic, I should also check against all previosly produced primes. — Konstantin Dinev, Sep 14 '12 at 10:47
To follow up on my last sentence: if you use this "CheckIfProbablyPrime" function to make a list of candidate divisors, then it might not be a problem to have a few pseudoprimes in there. If you're testing divisibility in increasing order **and removing all the factors you find**, by construction any pseudoprime which divides the original number will already have had its factors removed, and so won't divide the remainder. — DSM, Sep 14 '12 at 10:47

Ben Ruijl · Accepted Answer · 2012-09-14T09:53:20.080

25

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.

edited Sep 14 '12 at 09:53

answered Sep 14 '12 at 09:47

Ben Ruijl

4,973
3
31
44

My first thought was about prime divisors, too, but I'm not sure that their search is faster, than straightforward division of N by all the numbers - we'll still be making sieve until sqrt(N) and then spend O(1) for each combination of primes (we will still have to travel through it). – Boris Burkov Sep 14 '12 at 10:10
I added a small modification to my question. So if I use my current primality test would this be efficient enough, or should I change my test? – Konstantin Dinev Sep 14 '12 at 10:10
@Bob, the prime list could be precomputed and has to be done only once even if multiple numbers have to be checked. The advantage of factorization is that only primes are checked. For one number you're right, it won't matter much. – Ben Ruijl Sep 14 '12 at 10:18
This is a good solution. I used it in my problem. However one mistake in this algorithm is that it will get stuck in an infinite loop. The fix is to create a copy of the div list in divisors method and run the inner nested loop on that. P.S - I ran the problem in Java and not Python and my experience is based on that. – Pawan Mar 25 '14 at 09:47
1

@Pawan, this is probably because you update the div list itself in the for loop over the div, and then you get an infinite loop. If you use a list comprehension, div is only updated after the entire new div list has been created. – Ben Ruijl Mar 26 '14 at 08:43

score 3 · Answer 2 · answered Sep 14 '12 at 09:44

3

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.

answered Sep 14 '12 at 09:44

raina77ow

103,633
15
192
229

Also try appending the results to a string instead of a list. – Burhan Khalid Sep 14 '12 at 09:47
This is code optimization, fine, but you will have the same "big O". Ben Ruijl solution really reduce algorithm complexity and so the time taken for big numbers. – MatthieuW Sep 14 '12 at 10:03

score 1 · Answer 3 · answered Sep 14 '12 at 09:48

1

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

answered Sep 14 '12 at 09:48

MatthieuW

2,292
15
25

score 0 · Answer 4 · answered Sep 14 '12 at 09:48

0

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.

answered Sep 14 '12 at 09:48

MikeFHay

8,562
4
31
52

3

In Python 3, it doesn't. There you can use `//` for floor division. – Tim Pietzcker Sep 14 '12 at 09:53

Finding all divisors of a number optimization

4 Answers4

Linked