**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