Check if count of divisors is even or odd - GeeksforGeeks
Given a number "n", find its total number of divisors are even or odd.
Read full article from Check if count of divisors is even or odd - GeeksforGeeks
Given a number "n", find its total number of divisors are even or odd.
We can observe that the number of divisors is odd only in case of perfect squares. Hence the best solution would be to check if the given number is perfect square or not. If it’s a perfect square, then the number of divisors would be odd, else it’d be even.
void
countDivisors(
int
n)
{
int
root_n =
sqrt
(n);
// If n is a perfect square, then
// it has odd divisors
if
(root_n*root_n == n)
printf
(
"Odd\n"
);
else
printf
(
"Even\n"
);
}
A naive approach would be to find all the divisors and then see if the total number of divisors is even or odd.
Time complexity for such a solution would be O(sqrt(n))
void
countDivisors(
int
n)
{
// Initialize count of divisors
int
count = 0;
// Note that this loop runs till square root
for
(
int
i=1; i<=
sqrt
(n)+1; i++)
{
if
(n%i==0)
// If divisors are equal,increment
// count by one
// Otherwise increment count by 2
count += (n/i == i)? 1 : 2;
}
if
(count%2==0)
printf
(
"Even\n"
);
else
printf
(
"Odd\n"
);
}