Elementtien määrä parittomilla kertoimilla tietyllä alueella
#practiceLinkDiv { näyttö: ei mitään !tärkeää; } Annettu alue [ n m ] etsi elementtien lukumäärä, joilla on pariton määrä tekijöitä annetulla alueella ( n ja m mukaan lukien).
Esimerkkejä:
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 Yksinkertainen Ratkaisu on käydä läpi kaikki numerot alkaen n . Tarkista jokaisen luvun kohdalla, onko sillä parillinen määrä tekijöitä. Jos siinä on parillinen määrä tekijöitä, lisää tällaisten lukujen määrää ja tulosta lopuksi tällaisten elementtien lukumäärä. Löytääksesi kaikki luonnollisen luvun jakajat tehokkaasti viitata Kaikki luonnollisen luvun jakajat
An Tehokas Ratkaisu on tarkkailla kuviota. Vain ne numerot, jotka ovat täydelliset neliöt on pariton määrä tekijöitä. Analysoidaan tätä mallia esimerkin avulla.
Esimerkiksi 9:ssä on pariton määrä kertoimia 1 3 ja 9. 16:lla on myös pariton määrä tekijöitä 1 2 4 8 16. Syy tähän on, että muiden lukujen kuin täydellisten neliöiden kaikki tekijät ovat parien muodossa, mutta täydellisillä neliöillä yksi tekijä on yksi ja tekee kokonaissummasta parittoman.
Kuinka löytää täydellisten neliöiden lukumäärä alueella?
Vastaus on ero neliöjuuren välillä m ja n-1 ( ei n )
On pieni varoitus. Kuten molemmat n ja m ovat osallisia, jos n on täydellinen neliö, saamme vastauksen, joka on pienempi kuin yksi todellinen vastaus. Tämän ymmärtämiseksi harkitse vaihteluväliä [4 36]. Vastaus on 5 eli numerot 4 9 16 25 ja 36.
Mutta jos teemme (36**0.5) - (4**0.5), saamme 4. Joten tämän semanttisen virheen välttämiseksi otamme 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>
Lähtö:
Count is 8
Aika monimutkaisuus: O(1)
Aputila: O(1)
