Počet prvkov s nepárnymi faktormi v danom rozsahu
#practiceLinkDiv { display: none !important; } Vzhľadom na rozsah [ n m ] nájsť počet prvkov, ktoré majú nepárny počet faktorov v danom rozsahu ( n a m vrátane).
Príklady:
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 Jednoduché riešenie je prechádzať cez všetky čísla začínajúce od n . Pre každé číslo skontrolujte, či má párny počet faktorov. Ak má párny počet faktorov, zvýšte počet takýchto čísel a nakoniec vypíšte počet takýchto prvkov. Ak chcete efektívne nájsť všetkých deliteľov prirodzeného čísla Všetky delitele prirodzeného čísla
An Efektívne riešenie je sledovať vzorec. Iba tie čísla, ktoré sú dokonalé štvorce majú nepárny počet faktorov. Analyzujme tento vzorec na príklade.
Napríklad 9 má nepárny počet faktorov 1 3 a 9. 16 má tiež nepárny počet faktorov 1 2 4 8 16. Dôvodom je to, že pre čísla iné ako dokonalé štvorce sú všetky faktory vo forme párov, ale pre dokonalé štvorce je jeden faktor jediný a celkový súčet je nepárny.
Ako nájsť počet dokonalých štvorcov v rozsahu?
Odpoveď je rozdiel medzi druhou odmocninou z m a n-1 ( nie n )
Je tu malé upozornenie. Ako oboje n a m sú inkluzívne, ak n je dokonalý štvorec, dostaneme odpoveď, ktorá je menšia ako jedna skutočná odpoveď. Aby ste to pochopili, zvážte rozsah [4 36]. Odpoveď je 5, teda čísla 4 9 16 25 a 36.
Ale ak to urobíme (36**0,5) - (4**0,5), dostaneme 4. Aby sme sa vyhli tejto sémantickej chybe, 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>
výstup:
Count is 8
Časová zložitosť: O(1)
Pomocný priestor: O(1)
