Кількість елементів із непарними факторами в заданому діапазоні
#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 .
// 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)
