Straight Developer

1. CountFactors
Count factors of given number n.

Here comes the first task of the lesson 10: prime and composite numbers on Codility, the task is CountFactors and it’s probably the easiest of all the four tasks in this lessons serie, the others being: Flags, MinPerimeterRectangle and Peaks. You can find the 100% score solution of each one them in my other posts !
The solution I am going to share with you is a javascript based function and has a time complexity of O(sqrt(N)), first things first, here’s the task description on Codility:

Codility Prime and composite numbers: CountFactors task description

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

function solution(N);

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..2,147,483,647]

Counting the divisors that are lower than the square root of the number

The solution is very simple and straightforward and it has already been explained in the “reading materiel (pdf)” you can find in the prime and composite numbers lesson page, to obtain the number of factors of a number n, we simply count how much divisors are there before we reach the root square of n ( √n ), that’s because √n splits n’s factors into two equal groups, for example let’s take the number 100, so √n would be 10 right? here’s the list of all the factors of n:

1, 2, 5, 10, 20, 50, 100

as you can see, there are exactly as much factors in the left of 10 as in the right which means that there is a smart solution that would use half performances comparing to the most obvious solution which is to loop on every number lower than n and test if it’s a divisor or not.
knowing that, we can simply increment our counter by 2 instead of 1 each time we encounter a divisor then stop as soon as we reach the square root:

var root=Math.sqrt(N)    
for(var i=1;i<=root;i++){ 
}

then we test if i is a divisor of n on each iteration using the modulus operator (%)

 var root=Math.sqrt(N)    
 for(var i=1;i<=root;i++){ 
   if(N%i==0)
    factors+=2; 
 } 

but that’s not enough yet because when the square root is a factor then it needs to be counted too, but you only add one to the counter this time, because if the square root is a factor then its symmetric factor would be the square root itself, after all √n * √n = n

if(i==root)
  factors++
else
  factors+=2;

Keep in mind that the square root of n can only be a factor only if it’s a whole number which is not the case when n=10 for example.
Here’s the final javascript code:

function solution(N) {
    var factors=0
    var root=Math.sqrt(N)
    for(var i=1;i<=root;i++){
        if(N%i==0)
            if(i==root)
                factors++
            else
                factors+=2;
    }
    return factors
}