Število elementov z lihimi faktorji v danem območju
#practiceLinkDiv { display: none !important; } Glede na obseg [ n m ] poiščite število elementov, ki imajo liho število faktorjev v danem območju ( n in m vključno).
Primeri:
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 Preprosta rešitev je prelistati vse številke, začenši s n . Za vsako število preverite, ali ima sodo število faktorjev. Če ima sodo število faktorjev, povečaj število takih števil in na koncu izpiši število takih elementov. Za učinkovito iskanje vseh deliteljev naravnega števila uporabite Vsi delitelji naravnega števila
An Učinkovita rešitev je opazovati vzorec. Samo tiste številke, ki so popolni kvadrati imajo liho število faktorjev. Analizirajmo ta vzorec na primeru.
Na primer, 9 ima liho število faktorjev 1 3 in 9. 16 ima prav tako liho število faktorjev 1 2 4 8 16. Razlog za to je, da so vsi faktorji pri številih, razen popolnih kvadratov, v obliki parov, pri popolnih kvadratih pa je en faktor en sam, zato je vsota liha.
Kako najti število popolnih kvadratov v obsegu?
Odgovor je razlika med kvadratnim korenom m in n-1 ( ne n )
Obstaja majhno opozorilo. Kot oboje n in m so vključujoče, če n je popoln kvadrat, bomo dobili odgovor, ki je manjši od dejanskega odgovora. Da bi to razumeli, upoštevajte obseg [4 36]. Odgovor je 5, tj. številki 4 9 16 25 in 36.
Če pa naredimo (36**0,5) - (4**0,5), dobimo 4. Da bi se izognili tej semantični napaki, vzamemo 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>
Izhod:
Count is 8
Časovna zapletenost: O(1)
Pomožni prostor: O(1)
