Numărul de elemente cu factori impari într-un interval dat
#practiceLinkDiv { display: none !important; } Având în vedere un interval [ n m ] găsiți numărul de elemente care au un număr impar de factori în intervalul dat ( n şi m inclusiv).
Exemple:
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
O Soluție simplă este să faci bucla prin toate numerele începând de la n . Pentru fiecare număr verificați dacă are un număr par de factori. Dacă are un număr par de factori, atunci creșteți numărul acestor numere și, în final, imprimați numărul acestor elemente. Pentru a găsi toți divizorii unui număr natural, consultați eficient Toți divizorii unui număr natural
Un Soluție eficientă este de a observa modelul. Doar acele numere care sunt Pătrate perfecte au un număr impar de factori. Să analizăm acest tipar printr-un exemplu.
De exemplu, 9 are un număr impar de factori 1 3 și 9. 16 are, de asemenea, un număr impar de factori 1 2 4 8 16. Motivul este pentru alte numere decât pătratele perfecte, toți factorii sunt sub formă de perechi, dar pentru pătratele perfecte un factor este unic și face ca totalul să fie impar.
Cum să găsiți numărul de pătrate perfecte într-un interval?
Răspunsul este diferența dintre rădăcina pătrată a m şi n-1 ( nu n )
Există un mic avertisment. Ca amândoi n şi m sunt incluzive dacă n este un pătrat perfect, vom obține un răspuns care este mai mic decât unul răspunsul real. Pentru a înțelege acest lucru, luați în considerare intervalul [4 36]. Răspunsul este 5, adică numerele 4 9 16 25 și 36.
Dar dacă facem (36**0.5) - (4**0.5) obținem 4. Deci, pentru a evita această eroare semantică luăm 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>
Ieșire:
Count is 8
Complexitatea timpului: O(1)
Spațiu auxiliar: O(1)
