주어진 범위에서 홀수 인자를 갖는 요소의 수
#practiceLinkDiv { 표시: 없음 !중요; } 범위가 주어지면 [ N 중 ] 주어진 범위에서 홀수 개의 요소를 갖는 요소 수를 찾습니다( N 그리고 중 포함한).
예:
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
에이 간단한 솔루션 다음부터 시작하는 모든 숫자를 반복하는 것입니다. N . 모든 숫자에 대해 요소 개수가 짝수인지 확인하세요. 요소 수가 짝수이면 해당 숫자의 개수를 늘리고 마지막으로 해당 요소의 수를 인쇄합니다. 자연수의 모든 약수를 효율적으로 찾으려면 다음을 참조하세요. 자연수의 모든 약수
안 효율적인 솔루션 패턴을 관찰하는 것입니다. 해당 숫자만 완벽한 사각형 홀수 개의 요인이 있습니다. 예를 통해 이 패턴을 분석해 보겠습니다.
예를 들어 9에는 1 3과 9의 홀수개의 인수가 있습니다. 16의 인수는 홀수인 1 2 4 8 16입니다. 그 이유는 완전제곱이 아닌 숫자의 경우 모든 인수가 쌍의 형태이지만 완전제곱의 경우 한 인수가 단일이므로 전체가 홀수가 되기 때문입니다.
범위에서 완전제곱수를 찾는 방법은 무엇입니까?
답은 제곱근의 차이입니다. 중 그리고 n-1 ( 아니 n )
약간의 주의사항이 있습니다. 둘 다로서 N 그리고 중 다음과 같은 경우에는 포함됩니다. N 완전제곱수는 실제 답보다 작은 답을 얻게 됩니다. 이를 이해하려면 범위 [4 36]를 고려하십시오. 답은 5, 즉 숫자 4 9 16 25 및 36입니다.
그러나 (36**0.5) - (4**0.5)를 수행하면 4를 얻습니다. 따라서 이 의미 오류를 피하기 위해 다음을 수행합니다. 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>
출력 :
Count is 8
시간 복잡도: 오(1)
보조 공간: 오(1)
