## 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.