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;
}

// Java program to count number of odd squares
// in given range [n, m]
 
import java.io.*;
import java.util.*;
import java.lang.*;
 
class GFG
{
    public static int countOddSquares(int n, int m)
    {
        return (int)Math.pow((double)m,0.5) - (int)Math.pow((double)n-1,0.5);
    }
    // Driver code for above functions
    public static void main (String[] args)
    {
        int n = 5, m = 100;
        System.out.print("Count is " + countOddSquares(n, m));
    }
}
// Mohit Gupta_OMG <(o_0)>

# Python program to count number of odd squares
# in given range [n, m]
 
def countOddSquares(n, m):
    return int(m**0.5) - int((n-1)**0.5)
 
# Driver code
n = 5
m = 100
print("Count is", countOddSquares(n, m))
 
# Mohit Gupta_OMG <0_o>

// C# program to count number of odd
// squares in given range [n, m]
using System;
 
class GFG {
     
    // Function to count odd squares
    public static int countOddSquares(int n, int m)
    {
        return (int)Math.Pow((double)m, 0.5) -
               (int)Math.Pow((double)n - 1, 0.5);
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 5, m = 100;
        Console.Write("Count is " + countOddSquares(n, m));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to count
// number of odd squares
// in given range [n, m]
 
function countOddSquares($n, $m)
{
return pow($m, 0.5) -
       pow($n - 1, 0.5);
}
 
// Driver code
$n = 5; $m = 100;
echo "Count is " ,
      countOddSquares($n, $m);
 
// This code is contributed
// by nitin mittal.
?>

<script>
 
// JavaScript program to count number of odd squares
// in given range [n, m]
 
function countOddSquares(n, m)
    {
        return Math.pow(m,0.5) - Math.pow(n-1,0.5);
    }
 
// Driver Code
 
        let n = 5, m = 100;
        document.write("Count is " + countOddSquares(n, m));
                         
</script>

Producción : 

Count is 8

Complejidad temporal: O(1)
Espacio auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi y Divyanshu Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.