Antal elementer med ulige faktorer i et givet interval
#practiceLinkDiv { display: ingen !important; } Givet en rækkevidde [ n m ] find antallet af elementer, der har ulige antal faktorer i det givne interval ( n og m inklusive).
Eksempler:
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
EN Simpel løsning er at gå gennem alle tal startende fra n . Tjek for hvert tal, om det har et lige antal faktorer. Hvis den har et lige antal faktorer, skal du øge antallet af sådanne tal og til sidst udskrive antallet af sådanne elementer. For at finde alle divisorer af et naturligt tal referer effektivt Alle divisorer af et naturligt tal
An Effektiv løsning er at observere mønsteret. Kun de tal, der er perfekte firkanter har et ulige antal faktorer. Lad os analysere dette mønster gennem et eksempel.
For eksempel 9 har ulige antal faktorer 1 3 og 9. 16 har også ulige antal faktorer 1 2 4 8 16. Årsagen til dette er for andre tal end perfekte kvadrater alle faktorer er i form af par, men for perfekte kvadrater er en faktor enkelt og gør totalen som ulige.
Hvordan finder man antallet af perfekte firkanter i et område?
Svaret er forskellen mellem kvadratroden af m og n-1 ( ikke n )
Der er en lille advarsel. Som begge dele n og m er inklusive hvis n er et perfekt kvadrat, får vi et svar, der er mindre end et af det faktiske svar. For at forstå dette skal du overveje rækkevidde [4 36]. Svaret er 5, dvs. tallene 4 9 16 25 og 36.
Men hvis vi gør (36**0,5) - (4**0,5) får vi 4. Så for at undgå denne semantiske fejl tager vi 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>
Output:
Count is 8
Tidskompleksitet: O(1)
Hjælpeplads: O(1)
