#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 .
aws червено отместванеC++
// 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>
Изход:
np.уникален
Count is 8
Времева сложност: О(1)
Помощно пространство: О(1)