CODEWITHSUNDEEP
c#.netlinqmath
Ben McCormack
Ben McCormack

Reputation: 33078

Find the number of divisors of a number given an array of prime factors using LINQ

Given an array of prime factors of a natural number, how can I find the total number of divisors using LINQ upon the original array? I've already figured out most of this problem, but I'm having trouble with my LINQ statement.

Math Background:

The prime factors of a number are the prime integers that divide evenly into the number without a remainder. e.g. The prime factors of 60 are 2,2,3,5.

The divisors of a number are all integers (prime or otherwise) that divide evenly into the number without a remainder. The divisors of 60 are 1,2,3,4,5,6,10,12,15,20,30,60.

I am interested in finding the total number of divisors. The total number of divisors for 60 is 12.

Let's express the prime factorization using exponents:

60 = 2^2 * 3^1 * 5*1

To find the total number of divisors given the prime factorization of the number, all we have to do is add 1 to each exponent and then multiply those numbers together, like so:

(2 + 1) * (1 + 1) * (1 + 1) = 12;

That's how you find the number of divisors given the prime factorization of a number.

The Code I Have So Far:

I already have good code to get the prime factors of a number, so I'm not concerned about that. Using LINQ, I want to figure out what the total number of divisors is. I could use a few loops, but I'm trying to use LINQ (if possible).

I'm going to:

Here's the code I have:

class Program
{
    static void Main(string[] args)
    {
        var primeFactors = new int[] { 2, 2, 3, 5 };
        Console.WriteLine(primeFactors.Distinct().PrintList("", ", "));
            //Prints: 2, 3, 5
        Console.WriteLine("[2]:{0} [3]:{1} [5]:{2}"
            , primeFactors.Count(x => x == 2)
            , primeFactors.Count(x => x == 3)
            , primeFactors.Count(x => x == 5)
            );
            //Prints: [2]:2 [3]:1 [5]:1

\\THIS IS WHERE I HAVE TROUBLE:

        Console.WriteLine(primeFactors.Distinct().Aggregate((total,next) =>  
            (primeFactors.Count(x => x ==next) + 1)* total));
            //Prints: 8


        Console.ReadLine();
    }
}

Specifically, I'm having trouble with this part of code:

primeFactors.Distinct().Aggregate((total,next) =>  
    (primeFactors.Count(x => x ==next) + 1)* total)

Since the numbers in my array are not stored in the form of x^n, but rather in the form of n instances of x in the array, my thinking is to use Count() to find what n ought to be on a distinct array of x. The Aggregate function is intended to iterate through each distinct item in the array, find its Count + 1, and then multiply that by the total. The lambda expression in Count is supposed to use each distinct number as a parameter (next).

The above code should return 12, but instead it returns 8. I have trouble "stepping through" LINQ in debug mode and I can't figure out how I might better write this.

Why doesn't that portion of my code return the correct number of divisors as I expect? Is there a different (better) way to express this using LINQ?

Upvotes: 1

Views: 3409

Answers (2)

LBushkin
LBushkin

Reputation: 131676

If I understand what you're looking to do, you may want to use GroupBy() instead.

var primeFactors = new int[]{ 2, 2, 3, 5 };
var numFacs = primeFactors.GroupBy(f => f, f => f, (g, s) => s.Count() + 1)
                          .Aggregate(1, (x, y) => x * y);

Upvotes: 2

Aviad P.
Aviad P.

Reputation: 32639

Try this:

int[] factors = new int[] { 2, 2, 3, 5 };
var q = from o in factors
        group o by o into g
        select g.Count() + 1;
var r = q.Aggregate((x, y) => x * y);

The specific problem with your suggested query is that your aggregate call fails to count the very first element (not to mention doesn't increment the count by 1). What it erroneously does is take the first factor and multiplies its value instead of its count + 1 with the next one.

Upvotes: 4

Related Questions