Liczba elementów o współczynnikach nieparzystych w danym zakresie
#practiceLinkDiv { display: none !important; } Biorąc pod uwagę zakres [ N M ] znajdź liczbę elementów, które mają nieparzystą liczbę współczynników w danym zakresie ( N I M włącznie).
Przykłady:
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 Proste rozwiązanie polega na przejrzeniu wszystkich liczb zaczynających się od N . Dla każdej liczby sprawdź, czy ma ona parzystą liczbę dzielników. Jeśli ma parzystą liczbę czynników, to zwiększ liczbę takich liczb i na koniec wypisz liczbę takich elementów. Aby skutecznie znaleźć wszystkie dzielniki liczby naturalnej, odwołaj się Wszystkie dzielniki liczby naturalnej
Jakiś Wydajne rozwiązanie jest przestrzeganie wzoru. Tylko te liczby, które są idealne kwadraty mają nieparzystą liczbę czynników. Przeanalizujmy ten wzór na przykładzie.
Na przykład 9 ma nieparzystą liczbę czynników 1 3 i 9. 16 ma również nieparzystą liczbę czynników 1 2 4 8 16. Dzieje się tak dlatego, że w przypadku liczb innych niż idealne kwadraty wszystkie czynniki mają postać par, ale w przypadku idealnych kwadratów jeden czynnik jest pojedynczy i suma jest nieparzysta.
Jak znaleźć liczbę idealnych kwadratów w zakresie?
Odpowiedzią jest różnica między pierwiastkiem kwadratowym z M I n-1 ( nie n )
Jest małe zastrzeżenie. Jako oba N I M są włącznie, jeśli N jest idealnym kwadratem, otrzymamy odpowiedź mniejszą niż jedna rzeczywista odpowiedź. Aby to zrozumieć, rozważ zakres [4 36]. Odpowiedź to 5, czyli liczby 4 9 16 25 i 36.
Ale jeśli tak zrobimy (36**0,5) - (4**0,5) otrzymamy 4. Aby uniknąć tego błędu semantycznego, bierzemy 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>
Wyjście :
Count is 8
Złożoność czasowa: O(1)
Przestrzeń pomocnicza: O(1)
