Numero di elementi con fattori dispari in un dato intervallo
#practiceLinkDiv { display: none! importante; } Dato un intervallo [ N M ] trova il numero di elementi che hanno un numero dispari di fattori nell'intervallo dato ( N E M compreso).
Esempi:
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
UN Soluzione semplice è scorrere tutti i numeri a partire da N . Per ogni numero controlla se ha un numero pari di fattori. Se ha un numero pari di fattori, incrementa il conteggio di tali numeri e infine stampa il numero di tali elementi. Per trovare tutti i divisori di un numero naturale fare riferimento in modo efficiente Tutti i divisori di un numero naturale
UN Soluzione efficiente è osservare lo schema. Solo quei numeri che lo sono quadrati perfetti avere un numero dispari di fattori. Analizziamo questo modello attraverso un esempio.
Ad esempio 9 ha un numero dispari di fattori 1 3 e 9. 16 ha anche un numero dispari di fattori 1 2 4 8 16. La ragione di ciò è che per i numeri diversi dai quadrati perfetti tutti i fattori sono sotto forma di coppie, ma per i quadrati perfetti un fattore è singolo e rende il totale dispari.
Come trovare il numero di quadrati perfetti in un intervallo?
La risposta è la differenza tra radice quadrata di M E n-1 ( non n )
C'è un piccolo avvertimento. Come entrambi N E M sono inclusivi se N è un quadrato perfetto, otterremo una risposta inferiore a quella effettiva. Per comprendere questo, consideriamo l'intervallo [4 36]. La risposta è 5 cioè i numeri 4 9 16 25 e 36.
Ma se facciamo (36**0.5) - (4**0.5) otteniamo 4. Quindi per evitare questo errore semantico prendiamo 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>
Produzione :
Count is 8
Complessità temporale: O(1)
Spazio ausiliario: O(1)
