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