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)?

Dauphine

Possible duplicate of Best way to find all factors of a given number in C# – Afebrile

I found this post also helpful - codereview.stackexchange.com/questions/237416/… – Probable

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

Breaststroke

I dont follow. Factors is the list of prime factors that I found? And since what I want is all combinations of the factors that multiply to less than or equal to to the number, there has to be a better way. – Dauphine

this does not really work though. currently, if a prime goes in more than itself times, this will not give the correct factors (this happens a lot, i.e. every time 9 is a factor...) – Dauphine

I dont need that... the fact that there are multiple copies of the prime in the returned list is more than enough, since i will need to get all the combinations whose product is less that the number anyway – Dauphine

Ah, I see what you mean. You'll need to get the Cartesian product as mentioned in another comment then... – Breaststroke

because i am reducing the number that i am trying to factor with every successful division. note that the incrementation does not take place if the division was successful. In addition, since the factor may be a product of 3 or more factors, it makes sense to do it this way. there is no reason why i should store them all seperate (for example, if 36 gave 1,2,4,3,9,18,36 3*9 would be bad, as it it not a factor, but is less than 36. no other combination would have that problem) – Dauphine

how does one get the Cartesian product of an unspecified number of elements? – Dauphine

After reading your other comment, I realized that getting the Cartesian product isn't what you really want either. – Breaststroke

so how do i find all combinations of elements that have less than a specific product? – Dauphine

You want to compute the power set of the prime factorizations. Suppose you have the number 32340. Then the factorization is { 2 ^ 2, 3, 5, 7 ^ 2, 11}. You can represent that as the set S = { (2, 0), (2, 1), (3, 0), (5, 0), (7, 0), (7, 1), (11, 0) }. You want to compute the power set of S which is the set of all subsets of S. Each element in S is going to be of the form { (x1, y1), (x2, y2), ... }. For each one of those sets you want to compute the number x1 * x2 * x3... See rosettacode.org/wiki/Power_Set – Breaststroke

I really dont see how that helps. I go from wanting to compute the combinations of a list, to wanting to compute the combinations of a list. if I wanted to take my current list, and put it into that form, i would just have to count the consecutive repetitions of each element... i just dont see how that helps at all. – Dauphine

what code (rosettacode.org/wiki/Power_Set does not seem to work...)? – Dauphine

where is the input passed (and what does the imput consist of)? – Dauphine

The primes variable is from your list of primes sense you said that you wanted to use that list. The 'output' is the HashSet. – Breaststroke

For anyone else viewing this, just remove the .x, and the code will work fine – Dauphine

@RodrickChapman excellent post. However, if n is zero and primes is an empty list of primes for n, this line var factor = p.Select(x => x.x).Aggregate(1, (x, y) => (x * y)); ends up generator a factor 1 which is incorrect. – Whacky

Answer 2

There has been a similar question before, which has an interesting solution using IEnumerable. If you want all the divisors and not the factors, and assuming you are using at least C# 3.0 you could use something like this:

static IEnumerable<int> GetDivisors(int n)
{
    return from a in Enumerable.Range(2, n / 2)
           where n % a == 0
           select a;                      
}

and then use it like this:

foreach(var divisor in GetDivisors(10))
    Console.WriteLine(divisor);

or, if you want a List, just:

List<int> divisors = GetDivisors(10).ToList();

Miramirabeau

again, that is a nice way of doing it brute force. but given that i have a list of the necessary primes, there is no reason to do it that way. – Dauphine

So, if you have all the prime factors of the number and just want all the combinations among them why not using a cartesian product, sort of: from x in primes from y in primes where x != y select x * y? This could solve your issue, provided that you have 1 in your prime numbers (otherwise a .Concat(primes) would solve that) – Miramirabeau

but the number of factors that I have to multiply is unknown. it could be three or more... – Dauphine

I see your point. What you are asking is a method for having all the possible combinations of prime factors that you already have. This could be solved by means of some combinatorial algorithm which, in my opinion, is not that simple to implement properly. Besides that, you risk to end up with a solution that, while trying to optimize the speed, risks to be less performant than a simpler approach, and far less readable. Perhaps you might want to consider writing a readable solution first, and then trying to optimize it if its performance is not acceptable for the given task. – Miramirabeau

This method doesn't work when you are searching factors of prime numbers. For example for n=5 it gives an empty list! – Mycobacterium

@NikolayKostov I haven't tried this code, but I think if Enumerable.Range(2, n / 2) is changed to Enumerable.Range(1, n / 2) then that problem will be fixed. – Wed