Número de elementos con factores impares en un rango dado
#practiceLinkDiv { mostrar: ninguno !importante; } Dado un rango [ norte metro ] encuentre el número de elementos que tienen un número impar de factores en el rango dado ( norte y metro inclusivo).
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
A Solución sencilla es recorrer todos los números a partir de norte . Para cada número comprueba si tiene un número par de factores. Si tiene un número par de factores, incremente el recuento 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.
Un Solución eficiente es observar el patrón. Sólo aquellos números que son cuadrados perfectos tener 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 están en forma de pares, pero para los 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 metro y n-1 ( no n )
Hay una pequeña advertencia. como ambos norte y metro son inclusivos si norte es un cuadrado perfecto obtendremos una respuesta que es menor que uno de 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. Entonces, para evitar este error semántico tomamos n-1 .
// C++ program to count number of odd squares // in given range [n m] #include 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 // 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)>
Python3 # 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# // 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. ?>
JavaScript < 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 del tiempo: O(1)
Espacio Auxiliar: O(1)
