Problem
Factors of
Solution
Method 1 - Using divisor function.
Let
If
Example
Here is the pseudocode
References - stackoverflow,
Thanks.
Given a number find the number of factors of that numberExample
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