Nedostatak broja
Isprobajte na GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Za broj n se kaže da je manjkav broj ako je zbroj svih djelitelja broja označen s djeliteljiZbroj(n) manja je od dvostruke vrijednosti broja n. A razlika između ove dvije vrijednosti naziva se nedostatak .
Matematički gledano, ako vrijedi donji uvjet, broj se smatra manjkavim:
divisorsSum(n) < 2 * n deficiency = (2 * n) - divisorsSum(n)
Prvih nekoliko manjkavih brojeva su:
1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 19 .....
Zadan je broj n, naš zadatak je pronaći je li taj broj Manjavi broj ili nije.
Primjeri:
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
A Jednostavno rješenje je ponoviti sve brojeve od 1 do n i provjeriti dijeli li broj n te izračunati zbroj. Provjerite je li taj zbroj manji od 2 * n ili nije.
Vremenska složenost ovog pristupa: O ( n )
Optimizirano rješenje:
Ako pažljivo promatramo, djelitelji broja n prisutni su u parovima. Na primjer, ako je n = 100, tada su svi parovi djelitelja: (1 100) (2 50) (4 25) (5 20) (10 10)
Koristeći ovu činjenicu možemo ubrzati naš program.
Prilikom provjere djelitelja morat ćemo paziti ako postoje dva jednaka djelitelja kao u slučaju (10 10). U tom slučaju ćemo uzeti samo jedan od njih u izračun zbroja.
Implementacija optimiziranog pristupa
// C++ program to implement an Optimized Solution // to check Deficient Number #include using namespace std ; // Function to calculate sum of divisors 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 <= 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 bool isDeficient ( int n ) { // Check if sum(n) < 2 * n return ( divisorsSum ( n ) < ( 2 * n )); } /* Driver program to test above function */ int main () { isDeficient ( 12 ) ? cout < < 'YES n ' : cout < < 'NO n ' ; isDeficient ( 15 ) ? cout < < 'YES n ' : cout < < 'NO n ' ; return 0 ; }
Java // 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
Python3 # 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# // 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 // 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 ) ? 'YES n ' : 'NO n ' ; echo ( $ds ); $ds = isDeficient ( 15 ) ? 'YES n ' : 'NO n ' ; echo ( $ds ); // This code is contributed by ajit;. ?>
JavaScript < 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>
Izlaz:
NO YES
Vremenska složenost: O(sqrt(n))
Pomoćni prostor: O(1)
Reference:
https://en.wikipedia.org/wiki/Deficient_number
