Efficiently Getting All Divisors of a Given Number

Efficiently getting all divisors of a given number

Factors are paired. 1 and 24, 2 and 12, 3 and 8, 4 and 6.

An improvement of your algorithm could be to iterate to the square root of num instead of all the way to num, and then calculate the paired factors using num / i.

Efficiently finding all divisors of a number

Since you already have a list of the prime factors, what you want to do is to compute the powerset of that list.

Now, one problem is that you might have duplicates in the list (e.g. the prime factors of 20 = 2 * 2 * 5), but sets don't allow duplicates. So, we can make each element of the list unique by projecting it to a structure of the form {x, y} where x is the prime and y is the index of the prime in the list.

var all_primes = primes.Select((x, y) => new { x, y }).ToList();

Now, all_primes is a list of the form {x, y} where x is the prime and y is the index in the list.

Then we compute the power set (definition of GetPowerSet below):

var power_set_primes = GetPowerSet(all_primes);

Hence, power_set_primes is an IEnumerable<IEnumerable<T>> where T is the anonymous type {x, y} where x and y are of type int.

Next, we compute the product of the each element in the power set

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

Putting it all together:

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates.
var power_set_primes = GetPowerSet(all_primes);
var factors = new HashSet<int>();

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

From http://rosettacode.org/wiki/Power_Set for implementations of powerset.

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

What is the most efficient way of finding all the factors of a number in Python?

from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

This will return all of the factors, very quickly, of a number n.

Why square root as the upper limit?

sqrt(x) * sqrt(x) = x. So if the two factors are the same, they're both the square root. If you make one factor bigger, you have to make the other factor smaller. This means that one of the two will always be less than or equal to sqrt(x), so you only have to search up to that point to find one of the two matching factors. You can then use x / fac1 to get fac2.

The reduce(list.__add__, ...) is taking the little lists of [fac1, fac2] and joining them together in one long list.

The [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 returns a pair of factors if the remainder when you divide n by the smaller one is zero (it doesn't need to check the larger one too; it just gets that by dividing n by the smaller one.)

The set(...) on the outside is getting rid of duplicates, which only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

What is the best way to get all the divisors of a number?

Given your factorGenerator function, here is a divisorGen that should work:

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

The overall efficiency of this algorithm will depend entirely on the efficiency of the factorGenerator.

Finding all divisors of a number optimization

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.

Algorithm to find all the exact divisors of a given integer

First, your code should have the condition of i <= n/2, otherwise it can miss one of the factors, for example 6 will not be printed if n=12.

Run the loop to the square root of the number (ie. i <= sqrt(n)) and print both i and n/i (both will be multiples of n).

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

Note :

• For a perfect square, so that the square root is not printed twice, the additional checking is done at the end of loop for i*i == n as suggested by @chepner.
• If you want all the factors in ascending order store the values in an array then at the end of the loop sort all the numbers and display.

---

Related Topics