Anzahl der Elemente mit ungeraden Faktoren in einem bestimmten Bereich
#practiceLinkDiv { display: none !important; } Gegeben ein Bereich [ N M ] Finden Sie die Anzahl der Elemente mit einer ungeraden Anzahl von Faktoren im angegebenen Bereich ( N Und M inklusive).
Beispiele:
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 Einfache Lösung besteht darin, alle Zahlen beginnend mit zu durchlaufen N . Überprüfen Sie für jede Zahl, ob sie eine gerade Anzahl von Faktoren hat. Wenn es eine gerade Anzahl von Faktoren hat, erhöhen Sie die Anzahl dieser Zahlen und geben Sie schließlich die Anzahl dieser Elemente aus. Um alle Teiler einer natürlichen Zahl effizient zu finden, siehe Alle Teiler einer natürlichen Zahl
Ein Effiziente Lösung ist, das Muster zu beobachten. Nur die Zahlen, die es gibt perfekte Quadrate haben eine ungerade Anzahl von Faktoren. Lassen Sie uns dieses Muster anhand eines Beispiels analysieren.
Zum Beispiel hat 9 eine ungerade Anzahl von Faktoren 1 3 und 9. 16 hat auch eine ungerade Anzahl von Faktoren 1 2 4 8 16. Der Grund dafür ist, dass bei anderen Zahlen als perfekten Quadraten alle Faktoren in Form von Paaren vorliegen, aber bei perfekten Quadraten ist ein Faktor einfach und macht die Summe ungerade.
Wie finde ich die Anzahl perfekter Quadrate in einem Bereich?
Die Antwort ist die Differenz zwischen der Quadratwurzel von M Und n-1 ( nicht n )
Es gibt eine kleine Einschränkung. Als beides N Und M sind inklusive, wenn N ein perfektes Quadrat ist, erhalten wir eine Antwort, die kleiner als eins der tatsächlichen Antwort ist. Um dies zu verstehen, betrachten Sie den Bereich [4 36]. Die Antwort ist 5, also die Zahlen 4, 9, 16, 25 und 36.
Aber wenn wir (36**0,5) - (4**0,5) machen, erhalten wir 4. Um diesen semantischen Fehler zu vermeiden, gehen wir also vor 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>
Ausgabe :
Count is 8
Zeitkomplexität: O(1)
Hilfsraum: O(1)
