Broj elemenata s neparnim faktorima u zadanom rasponu
#practiceLinkDiv { display: none !important; } S obzirom na raspon [ n m ] pronaći broj elemenata koji imaju neparan broj faktora u zadanom rasponu ( n i m uključivo).
Primjeri:
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 Jednostavno rješenje je proći kroz sve brojeve počevši od n . Za svaki broj provjerite ima li paran broj faktora. Ako ima paran broj faktora, povećajte broj takvih brojeva i na kraju ispišite broj takvih elemenata. Da biste pronašli sve djelitelje prirodnog broja učinkovito pogledajte Svi djelitelji prirodnog broja
An Učinkovito rješenje je promatrati obrazac. Samo oni brojevi koji jesu savršeni kvadrati imaju neparan broj faktora. Analizirajmo ovaj obrazac kroz primjer.
Na primjer, 9 ima neparan broj faktora 1 3 i 9. 16 također ima neparan broj faktora 1 2 4 8 16. Razlog za to je što su za brojeve osim savršenih kvadrata svi faktori u obliku parova, ali za savršene kvadrate jedan faktor je jedan i čini zbroj neparnim.
Kako pronaći broj savršenih kvadrata u nizu?
Odgovor je razlika između kvadratnog korijena od m i n-1 ( ne n )
Postoji malo upozorenje. Kao oboje n i m su uključivi ako n je savršeni kvadrat, dobit ćemo odgovor koji je manji od jedan stvarni odgovor. Da biste ovo razumjeli, razmotrite raspon [4 36]. Odgovor je 5, tj. brojevi 4 9 16 25 i 36.
Ali ako napravimo (36**0,5) - (4**0,5) dobit ćemo 4. Da bismo izbjegli ovu semantičku pogrešku, uzimamo 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>
Izlaz:
Count is 8
Vremenska složenost: O(1)
Pomoćni prostor: O(1)
