#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
Pratica consigliata Contare i fattori dispari Provalo!
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 .
amisha patelC++
// C++ program to count number of odd squares // in given range [n m] #include
// 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)m0.5) - (int)Math.pow((double)n-10.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 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(m0.5) - Math.pow(n-10.5); } // Driver Code let n = 5 m = 100; document.write('Count is ' + countOddSquares(n m)); </script>
Produzione :
linguaggio informatico groovy
Count is 8
Complessità temporale: O(1)
Spazio ausiliario: O(1)