Check If a Number Has Even or Odd Number of Factors

The code is based on the idea that if A is a factor of N, then B=N/A is also a factor of N.
Here A, B and N are natural numbers.

Let S be the square root of N.

example-1: 2 is a factor of 6, (6/2)=3 is also a factor of 6. [A=2,N=6,B=3,S=2.44494]
example-2: 5 is a factor of 15, (15/5)=3 is also a factor of 15. [A=5,N=15,B=3,S=3.87298]
example-3: 4 is a factor of 16, (16/4)=4 is also a factor of 16. [A=4,N=16,B=4,S=4]

One point to be noted here is that if A is less than S, then B will be greater than S and vice-versa.

But if A is equal to S, then B is also equal to S (i.e. B=A=S). This only happens if N is a perfect square.

EXAMPLE:

Checking all the factors of N=36,
1*36=36 (1 and 36 are factors of 36)
2*18=36 (2 and 18 are factors of 36)
3*12=36 (3 and 12 are factors of 36)
4*9=36 (4 and 9 are factors of 36)
6*6=36 (6 is factor of 36)
9*4=36 (9 and 4 are factors of 36)
12*3=36 (12 and 3 are factors of 36)
18*2=36 (18 and 2 are factors of 36)
36*1=36 (36 and 1 are factors of 36)

Here, 1,36,2,18,3,12,4 and 9 are already counted from 1*36=36, 2*18=36, 3*12=36 and 4*9=36.

So there is no need of considering them again in 9*4=36, 18*2=36, 12*3=36 and 36*1=36. [By closure property, a*b=b*a]

Now we can say that for-all A less than S, there will always be even number of factors in total.

The deciding factor is only when A is equal to S. In this case, we get only a single factor (as both A and B are equal), making the total no.of factors odd.

So it is sufficient if we check whether S is a factor of N. However, this happens only if N is a perfect square. The square root of a perfect square is always an integer.

So, checking if S is an integer gives us the solution.

LET US SEE THE CODE:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    double sq;
    cout << "Enter the number" << endl;
    cin >> N;
    sq=sqrt(N);	//finding the square root of N
    if(sq==(int)sq)	//checking if sq is integer
    {
        cout << "The number has odd no.of factors" << endl;
    }
    else
    {
        cout << "The number has even no.of factors" << endl;
    }
    return 0;
}

TEST CASE 1:

Enter the number

5

The number has even no.of factors

TEST CASE 2:

Enter the number

16

The number has odd no.of factors