Брой елементи с нечетни фактори в даден диапазон
#practiceLinkDiv { display: none !important; } Даден е диапазон [ п м ] намерете броя на елементите, които имат нечетен брой фактори в дадения диапазон ( п и м включително).
Примери:
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
А Просто решение е да преминете през всички числа, започвайки от п . За всяко число проверете дали има четен брой множители. Ако има четен брой фактори, увеличете броя на тези числа и накрая отпечатайте броя на тези елементи. За да намерите всички делители на естествено число, ефективно се отнасяйте Всички делители на естествено число
Ан Ефикасно решение е да наблюдавате модела. Само тези числа, които са перфектни квадрати имат нечетен брой фактори. Нека анализираме този модел чрез пример.
Например 9 има нечетен брой множители 1 3 и 9. 16 също има нечетен брой множители 1 2 4 8 16. Причината за това е, че за числа, различни от перфектни квадрати, всички фактори са под формата на двойки, но за перфектни квадрати един фактор е единичен и прави общата сума нечетна.
Как да намерите броя на перфектните квадрати в диапазон?
Отговорът е разликата между корен квадратен от м и n-1 ( не n )
Има малко предупреждение. Като и двете п и м са включени ако п е перфектен квадрат, ще получим отговор, който е по-малък от един от действителния отговор. За да разберете това, разгледайте диапазона [4 36]. Отговорът е 5, т.е. числата 4 9 16 25 и 36.
Но ако направим (36**0.5) - (4**0.5) получаваме 4. Така че, за да избегнем тази семантична грешка, вземаме 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>
Изход:
Count is 8
Времева сложност: О(1)
Помощно пространство: О(1)
