Programa C para Número de elementos con factores impares en un rango dado

Dado un rango [ n , m ], encuentra el número de elementos que tienen un número impar de factores en el rango dado ( n y m inclusive).

Ejemplos:

Input  : n = 5, m = 100
Output : 8
The numbers with odd factors are 9, 16, 25, 
36, 49, 64, 81 and 100

Input  : n = 8, m = 65
Output : 6

Input  : n = 10, m = 23500
Output : 150

Una solución simple es recorrer todos los números a partir de n . Para cada número, verifica si tiene un número par de factores. Si tiene un número par de factores, incremente el conteo de dichos números y finalmente imprima el número de dichos elementos. Para encontrar todos los divisores de un número natural de manera eficiente, consulte Todos los divisores de un número natural

Una solución eficiente es observar el patrón. Solo aquellos números que son cuadrados perfectos tienen un número impar de factores. Analicemos este patrón a través de un ejemplo.

Por ejemplo, 9 tiene un número impar de factores, 1, 3 y 9. 16 también tiene un número impar de factores, 1, 2, 4, 8, 16. La razón de esto es que, para números que no sean cuadrados perfectos, todos los factores son en forma de pares, pero para cuadrados perfectos, un factor es único y hace que el total sea impar.

¿Cómo encontrar el número de cuadrados perfectos en un rango?
La respuesta es la diferencia entre la raíz cuadrada de m y n-1 ( no n ).
Hay una pequeña advertencia. Como tanto n como m son inclusivos, si n es un cuadrado perfecto, obtendremos una respuesta menor que la respuesta real. Para entender esto, considere el rango [4, 36]. La respuesta es 5, es decir, los números 4, 9, 16, 25 y 36.
Pero si hacemos (36**0.5) – (4**0.5) obtenemos 4. Así que para evitar este error semántico, tomamos n-1 .

// C++ program to count number of odd squares
// in given range [n, m]
#include <bits/stdc++.h>
using namespace std;
  
int countOddSquares(int n, int m)
{
    return (int)pow(m, 0.5) - (int)pow(n - 1, 0.5);
}
  
// Driver code
int main()
{
    int n = 5, m = 100;
    cout << "Count is " << countOddSquares(n, m);
    return 0;
}

Count is 8

Complejidad de tiempo: O(1)

Consulte el artículo completo sobre Número de elementos con factores impares en un rango dado para obtener más detalles.