Nombre d'elements amb factors imparells en un interval donat
#practiceLinkDiv { mostrar: cap !important; } Donat un rang [ n m ] troba el nombre d'elements que tenen un nombre senar de factors en l'interval donat ( n i m inclòs).
Exemples:
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 Solució senzilla és recórrer tots els números a partir de n . Per a cada nombre comproveu si té un nombre parell de factors. Si té un nombre parell de factors, incrementeu el recompte d'aquests nombres i, finalment, imprimiu el nombre d'aquests elements. Per trobar tots els divisors d'un nombre natural de manera eficient, feu referència Tots els divisors d'un nombre natural
An Solució eficient és observar el patró. Només aquells números que ho són quadrats perfectes tenen un nombre imparell de factors. Analitzem aquest patró a través d'un exemple.
Per exemple, 9 té un nombre senar de factors 1 3 i 9. 16 també té un nombre senar de factors 1 2 4 8 16. La raó d'això és que per als nombres diferents dels quadrats perfectes tots els factors estan en forma de parells, però per als quadrats perfectes un factor és únic i fa que el total sigui senar.
Com trobar el nombre de quadrats perfectes en un rang?
La resposta és la diferència entre arrel quadrada de m i n-1 ( no n )
Hi ha una petita advertència. Com tots dos n i m són inclusius si n és un quadrat perfecte, obtindrem una resposta que és menys d'una la resposta real. Per entendre això, considereu el rang [4 36]. La resposta és 5, és a dir, els números 4 9 16 25 i 36.
Però si fem (36**0,5) - (4**0,5) obtenim 4. Així que per evitar aquest error semàntic prenem 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>
Sortida:
Count is 8
Complexitat temporal: O(1)
Espai auxiliar: O(1)
