#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 ( не п )
Є невелике застереження. Як обидва п і м є включними, якщо п є ідеальним квадратом, ми отримаємо відповідь, меншу за одиницю фактичної відповіді. Щоб зрозуміти це, розглянемо діапазон [4 36]. Відповідь: 5, тобто числа 4 9 16 25 і 36.
Але якщо ми робимо (36**0,5) - (4**0,5), ми отримуємо 4. Отже, щоб уникнути цієї семантичної помилки, ми беремо n-1 .
токенізатор рядків javaC++
// 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>
Вихід:
32-бітна архітектура проти 64-бітної
Count is 8
Часова складність: О(1)
Допоміжний простір: О(1)