Tuesday, March 25, 2014

Algorithm to find out number of factors of a number

Problem
Given a number find the number of factors of that number
Example
Factors of 18 are 1, 2, 3, 6, 9, 18.  Hence 6 factors.

Solution
Method 1 -  Using divisor function.
Let n be the given number.
If n = p1^e1 * p2^e2 * ... * pk^ek, where each p is a prime number, then the number of factors of n is (e1 + 1)*(e2 + 1)* ... *(ek + 1).

Example
24 = 2^(3)*3^(1)
therefore, number of factors d(24) = (3 + 1)(1 + 1) = 8. 
 
More here and here.

Here is the pseudocode
read given number in n
initial_n = n
num_factors = 1;
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number
{
    power = 0; // suppose the power i appears at is 0
    while (n % i == 0) // while we can divide n by i
    {
        n = n / i // divide it, thus ensuring we'll only check prime factors
        ++power // increase the power i appears at
    }
    num_factors = num_factors * (power + 1) // apply the formula
}

if (n > 1) // will happen for example for 14 = 2 * 7
{
    num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2
}

References - stackoverflow,

Thanks.

0 comments:

Post a Comment