c# - Efficiently finding all divisors of a number

Question

So I simply want to find all the divisors of a given number (excepting the number itself). Currently, I have this:

public static List<int> proper_divisors(int x)
{
    List<int> toreturn = new List<int>();
    toreturn.Add(1);
    int i = 0;
    int j=1;
    int z = 0;
    while (primes.ElementAt(i) < Math.Sqrt(x))
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            toreturn.Add(x / primes.ElementAt(i));
            j = 2;
            z = (int)Math.Pow(primes.ElementAt(i), 2);
            while (z < x)
            {
                if (x % z == 0)
                {
                    toreturn.Add(z);
                    toreturn.Add(x / z);
                    j++;
                    z = (int)Math.Pow(primes.ElementAt(i), j);
                }
                else
                {
                    z = x;
                }
            }
        }
        i++;
    }
    toreturn = toreturn.Distinct().ToList<int>();
    return toreturn;
}

where primes is a list of primes (assume it is correct, and is large enough). The algorithm works in the sense that it finds all the prime factors, but not all the factors (i.e. given 34534, it returns {1,2,17267,31,1114} but misses {62, 557} as 62 is a combination, and therefore misses 557 as well.

I have also tried just getting the prime factors of a number, but I don't know how to convert that into a list of all of the correct combinations.

The code for that algorithm is as follows:

public static List<int> prime_factors(int x)
{
    List<int> toreturn = new List<int>();
    int i = 0;
    while (primes.ElementAt(i) <= x)
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            x = x / primes.ElementAt(i);
        }
        else
        {
            i++;
        }
    }
    return toreturn;
}

Any ideas on how to fix the first one, or how to create the list of combinations from the second one (I would prefer that as it would be faster)?

Answer 1

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];
}