#practiceLinkDiv { 표시: 없음 !중요; }숫자 n은 다음과 같이 표시된 숫자의 모든 약수를 합한 경우 결함수라고 합니다. 제수합(n) 숫자 n의 두 배보다 작습니다. 그리고 이 두 값의 차이를 부족 .
수학적으로 아래 조건이 충족되면 숫자가 부족하다고 합니다.
divisorsSum(n) < 2 * n deficiency = (2 * n) - divisorsSum(n)
처음 몇 개의 부족한 숫자는 다음과 같습니다.
1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 19 .....
숫자 n이 주어지면 우리의 임무는 이 숫자가 부족한 숫자인지 아닌지를 찾는 것입니다.
예:
Input: 21 Output: YES Divisors are 1 3 7 and 21. Sum of divisors is 32. This sum is less than 2*21 or 42. Input: 12 Output: NO Input: 17 Output: YES
권장 실습 부족한 숫자 시도해 보세요!
에이 간단한 솔루션 1부터 n까지 모든 숫자를 반복하고 숫자가 n으로 나뉘는지 확인하고 합계를 계산하는 것입니다. 이 합이 2 * n보다 작은지 확인하세요.
이 접근 방식의 시간 복잡도: O(n)
최적화된 솔루션:
주의 깊게 살펴보면 n의 약수가 쌍으로 존재합니다. 예를 들어 n = 100이면 모든 약수 쌍은 다음과 같습니다. (1 100) (2 50) (4 25) (5 20) (10 10)
이 사실을 이용하면 프로그램 속도를 높일 수 있습니다.
제수를 확인할 때 (10 10)의 경우처럼 두 개의 동일한 제수가 있는지 주의해야 합니다. 이 경우 합계 계산 시 둘 중 하나만 사용합니다.
최적화된 접근방식 구현
// C++ program to implement an Optimized Solution // to check Deficient Number #include
// Java program to check Deficient Number import java.io.*; class GFG { // Function to calculate sum of divisors static int divisorsSum(int n) { int sum = 0; // Initialize sum of prime factors // Note that this loop runs till square root of n for (int i = 1; i <= (Math.sqrt(n)); i++) { if (n % i == 0) { // If divisors are equal take only one // of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number static boolean isDeficient(int n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } /* Driver program to test above function */ public static void main(String args[]) { if (isDeficient(12)) System.out.println('YES'); else System.out.println('NO'); if (isDeficient(15)) System.out.println('YES'); else System.out.println('NO'); } } // This code is contributed by Nikita Tiwari
# Python program to implement an Optimized # Solution to check Deficient Number import math # Function to calculate sum of divisors def divisorsSum(n) : sum = 0 # Initialize sum of prime factors # Note that this loop runs till square # root of n i = 1 while i<= math.sqrt(n) : if (n % i == 0) : # If divisors are equal take only one # of them if (n // i == i) : sum = sum + i else : # Otherwise take both sum = sum + i; sum = sum + (n // i) i = i + 1 return sum # Function to check Deficient Number def isDeficient(n) : # Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)) # Driver program to test above function if ( isDeficient(12) ): print ('YES') else : print ('NO') if ( isDeficient(15) ) : print ('YES') else : print ('NO') # This Code is contributed by Nikita Tiwari
// C# program to implement an Optimized Solution // to check Deficient Number using System; class GFG { // Function to calculate sum of // divisors static int divisorsSum(int n) { // Initialize sum of prime factors int sum = 0; // Note that this loop runs till // square root of n for (int i = 1; i <= (Math.Sqrt(n)); i++) { if (n % i == 0) { // If divisors are equal // take only one of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number static bool isDeficient(int n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } /* Driver program to test above function */ public static void Main() { string var = isDeficient(12) ? 'YES' : 'NO'; Console.WriteLine(var); string var1 = isDeficient(15) ? 'YES' : 'NO'; Console.WriteLine(var1); } } // This code is contributed by vt_m
// PHP program to implement // an Optimized Solution // to check Deficient Number // Function to calculate // sum of divisors function divisorsSum($n) { // Initialize sum of // prime factors $sum = 0; // Note that this loop runs // till square root of n for ($i = 1; $i <= sqrt($n); $i++) { if ($n % $i==0) { // If divisors are equal // take only one of them if ($n / $i == $i) { $sum = $sum + $i; } // Otherwise take both else { $sum = $sum + $i; $sum = $sum + ($n / $i); } } } return $sum; } // Function to check // Deficient Number function isDeficient($n) { // Check if sum(n) < 2 * n return (divisorsSum($n) < (2 * $n)); } // Driver Code $ds = isDeficient(12) ? 'YESn' : 'NOn'; echo($ds); $ds = isDeficient(15) ? 'YESn' : 'NOn'; echo($ds); // This code is contributed by ajit;. ?> <script> // Javascript program to check Deficient Number // Function to calculate sum of divisors function divisorsSum(n) { let sum = 0; // Initialize sum of prime factors // Note that this loop runs till square root of n for (let i = 1; i <= (Math.sqrt(n)); i++) { if (n % i == 0) { // If divisors are equal take only one // of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number function isDeficient(n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } // Driver code to test above methods if (isDeficient(12)) document.write('YES' + '
'); else document.write('NO' + '
'); if (isDeficient(15)) document.write('YES' + '
'); else document.write('NO' + '
'); // This code is contributed by avijitmondal1998. </script>
출력 :
NO YES
시간 복잡도: O(제곱(n))
보조 공간 : 오(1)
참고자료 :
https://en.wikipedia.org/wiki/Deficient_number