Počet prvků s lichými faktory v daném rozsahu
#practiceLinkDiv { display: none !important; } Vzhledem k rozsahu [ n m ] najděte počet prvků, které mají lichý počet faktorů v daném rozsahu ( n a m včetně).
Pří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é řešení je procházet všemi čísly počínaje n . U každého čísla zkontrolujte, zda má sudý počet faktorů. Pokud má sudý počet faktorů, pak počet takových čísel zvýší a nakonec vytiskne počet takových prvků. Chcete-li efektivně najít všechny dělitele přirozeného čísla Všichni dělitelé přirozeného čísla
An Efektivní řešení je sledovat vzorec. Pouze ta čísla, která jsou dokonalé čtverce mají lichý počet faktorů. Pojďme analyzovat tento vzorec na příkladu.
Například 9 má lichý počet faktorů 1 3 a 9. 16 má také lichý počet faktorů 1 2 4 8 16. Důvodem je to, že u jiných čísel než dokonalých čtverců jsou všechny faktory ve formě párů, ale u dokonalých čtverců je jeden faktor jediný a činí součet lichým.
Jak najít počet dokonalých čtverců v rozsahu?
Odpověď je rozdíl mezi druhou odmocninou z m a n-1 ( ne n )
Existuje malé upozornění. Jako obojí n a m jsou včetně, pokud n je dokonalý čtverec, dostaneme odpověď, která je menší než jedna skutečná odpověď. Abyste tomu porozuměli, zvažte rozsah [4 36]. Odpověď je 5, tedy čísla 4 9 16 25 a 36.
Ale pokud to uděláme (36**0,5) - (4**0,5), dostaneme 4. Abychom se vyhnuli této sémantické chybě, vezmeme 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á náročnost: O(1)
Pomocný prostor: O(1)
