Programa en C para verificar si el conteo de divisores es par o impar

Dado un número “n”, encuentra si el número total de divisores es par o impar. Ejemplos:

Input  : n = 10      
Output : Even

Input:  n = 100
Output: Odd

Input:  n = 125
Output: Even

Un enfoque ingenuo sería encontrar todos los divisores y luego ver si el número total de divisores es par o impar. La complejidad del tiempo para tal solución sería O(sqrt(n)) 

// Naive Solution to
// find if count of
// divisors is even
// or odd
#include <math.h>
#include <stdio.h>
 
// Function to count
// the divisors
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");
}
 
/* Driver program to test above function */
int main()
{
    printf("The count of divisor: ");
    countDivisors(10);
    return 0;
}

The count of divisor: Even

Complejidad del tiempo: O(sqrt(n))

Espacio auxiliar : O(1)

Solución Eficiente: Podemos observar que el número de divisores es impar solo en el caso de los cuadrados perfectos. Por lo tanto, la mejor solución sería verificar si el número dado es un cuadrado perfecto o no. Si es un cuadrado perfecto, entonces el número de divisores sería impar, de lo contrario sería par. 

// C++ program for
// Efficient Solution to find
// if count of divisors is
// even or odd
#include <bits/stdc++.h>
using namespace std;
 
// Function to find if count
// of divisors is even or
// odd
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");
}
 
/* Driver program to test above function */
int main()
{
    cout << "The count of divisors of 10 is: \n";
 
    countDivisors(10);
    return 0;
}

The count of divisors of 10 is: 
Even

Complejidad del tiempo:O(1)

Consulte el artículo completo sobre Comprobar si el recuento de divisores es par o impar para obtener más detalles.