Número de elementos con factores pares en el rango dado

Dado un rango [n, m], la tarea es encontrar el número de elementos que tienen un número par de factores en el rango dado (n y m inclusive).
Ejemplos: 
 

Input: n = 5, m = 20
Output: 14
The numbers with even factors are 
5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20.

Input: n = 5, m = 100
Output: 88

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 encontrar los números con un número impar de factores , es decir, solo los cuadrados perfectos tienen un número impar de factores, por lo que todos los números que no sean cuadrados perfectos tendrán número par de factores. Por lo tanto, encuentre la cantidad de cuadrados perfectos en el rango y reste de los números totales, es decir, m-n+1 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the perfect squares
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 "
         << (m - n + 1) - countOddSquares(n, m);
    return 0;
}

// Java implementation of the above approach
import java.io.*;
 
class GFG
{
     
// Function to count the perfect squares
static int countOddSquares(int n, int m)
{
    return (int)Math.pow(m, 0.5) -
            (int)Math.pow(n - 1, 0.5);
}
 
// Driver code
public static void main (String[] args)
{
    int n = 5, m = 100;
    System.out.println("Count is " + ((m - n + 1)
                    - countOddSquares(n, m)));
}
}
 
// This code is contributed by ajit..

# Python3 implementation of the
# above approach
 
# Function to count the perfect squares
def countOddSquares(n, m) :
    return (int(pow(m, 0.5)) -
            int(pow(n - 1, 0.5)))
 
# Driver code
if __name__ == "__main__" :
 
    n = 5 ; m = 100;
    print("Count is", (m - n + 1) -
                       countOddSquares(n, m))
     
# This code is contributed by Ryuga

// C# implementation of the above approach
using System;
 
class GFG
{
         
// Function to count the perfect squares
static int countOddSquares(int n, int m)
{
    return (int)Math.Pow(m, 0.5) -
            (int)Math.Pow(n - 1, 0.5);
}
 
// Driver code
static public void Main ()
{
    int n = 5, m = 100;
    Console.WriteLine("Count is " + ((m - n + 1)
                    - countOddSquares(n, m)));
}
}
 
// This Code is contributed by akt_mit.

<?php
// PHP implementation of the
// above approach
 
// Function to count the perfect squares
function countOddSquares($n, $m)
{
    return (int)pow($m, 0.5) -
           (int)pow($n - 1, 0.5);
}
 
// Driver code
$n = 5;
$m = 100;
echo "Count is ", ($m - $n + 1) -
                   countOddSquares($n, $m);
     
// This code is contributed by ajit
?>

<script>
 
// Javascript implementation of the above approach
 
// Function to count the perfect squares
function countOddSquares(n, m)
{
    return Math.pow(m,0.5) - Math.pow(n - 1, 0.5);
}
 
// Driver code
var n = 5, m = 100;
document.write( "Count is "
     + ((m - n + 1) - countOddSquares(n, m)));
 
</script>

Count is 88

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)