Páratlan faktorú elemek száma adott tartományban
#practiceLinkDiv { display: none !important; } Adott egy tartomány [ n m ] keresse meg azoknak az elemeknek a számát, amelyek páratlan számú tényezővel rendelkeznek az adott tartományban ( n és m beleértve).
Példák:
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 Egyszerű Megoldás az, hogy az összes számot végighurkolja, kezdve n . Minden számnál ellenőrizze, hogy van-e páros számú tényezője. Ha páros számú tényezővel rendelkezik, akkor növelje az ilyen számok számát, és végül írja ki az ilyen elemek számát. Egy természetes szám összes osztójának hatékony megtalálásához hivatkozzon Egy természetes szám minden osztója
An Hatékony megoldás a minta megfigyelése. Csak azok a számok, amelyek tökéletes négyzetek páratlan számú tényezője van. Elemezzük ezt a mintát egy példán keresztül.
Például a 9-nek páratlan számú faktora van 1 3 és 9. 16 páratlan számú tényezője 1 2 4 8 16. Ennek az az oka, hogy a tökéletes négyzetektől eltérő számok esetén minden tényező pár formájában van, de a tökéletes négyzetek esetében az egyik tényező egyszeres, és az összértéket páratlannak adja.
Hogyan lehet megtalálni a tökéletes négyzetek számát egy tartományban?
A válasz a négyzetgyök közötti különbség m és n-1 ( nem n )
Van egy kis figyelmeztetés. Mint mindkettő n és m inkluzívak, ha n egy tökéletes négyzet, olyan választ kapunk, amely kisebb, mint eggyel a tényleges válasz. Ennek megértéséhez vegye figyelembe a tartományt [4 36]. A válasz 5, azaz a 4 9 16 25 és 36 számok.
De ha így teszünk (36**0,5) - (4**0,5), akkor 4-et kapunk. Tehát a szemantikai hiba elkerülése érdekében 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>
Kimenet:
Count is 8
Időbeli összetettség: O(1)
Kiegészítő tér: O(1)
