Número de elementos com fatores ímpares em determinado intervalo
#practiceLinkDiv { display: nenhum! Importante; } Dado um intervalo [ n eu ] encontre o número de elementos que possuem um número ímpar de fatores no intervalo determinado ( n e eu inclusivo).
Exemplos:
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
UM Solução Simples é percorrer todos os números começando em n . Para cada número verifique se ele possui um número par de fatores. Se tiver um número par de fatores, aumente a contagem desses números e, finalmente, imprima o número de tais elementos. Para encontrar todos os divisores de um número natural com eficiência, consulte Todos os divisores de um número natural
Um Solução Eficiente é observar o padrão. Somente os números que são quadrados perfeitos tem um número ímpar de fatores. Vamos analisar esse padrão por meio de um exemplo.
Por exemplo, 9 tem um número ímpar de fatores 1 3 e 9. 16 também tem um número ímpar de fatores 1 2 4 8 16. A razão para isso é que para números diferentes de quadrados perfeitos todos os fatores estão na forma de pares, mas para quadrados perfeitos um fator é único e torna o total ímpar.
Como encontrar o número de quadrados perfeitos em um intervalo?
A resposta é a diferença entre a raiz quadrada de eu e n-1 ( não )
Há uma pequena advertência. Como ambos n e eu são inclusivos se n é um quadrado perfeito, obteremos uma resposta menor que a resposta real. Para entender isso, considere o intervalo [4 36]. A resposta é 5, ou seja, números 4 9 16 25 e 36.
Mas se fizermos (36**0,5) - (4**0,5) obtemos 4. Então, para evitar esse erro 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>
Saída :
Count is 8
Complexidade de tempo: O(1)
Espaço Auxiliar: O(1)
