Pomanjkljivo število
Preizkusite na GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Za število n pravimo, da je pomanjkljivo število, če je vsota vseh deliteljev števila, označenega z deliteljiVsota(n) je manjša od dvakratne vrednosti števila n. In razlika med tema dvema vrednostma se imenuje pomanjkanje .
Matematično gledano, če spodnji pogoj velja, je število pomanjkljivo:
divisorsSum(n) < 2 * n deficiency = (2 * n) - divisorsSum(n)
Prvih nekaj pomanjkljivih številk je:
1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 19 .....
Za podano število n je naša naloga ugotoviti, ali je to število pomanjkljivo število ali ne.
Primeri:
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 Preprosta rešitev je ponoviti vsa števila od 1 do n in preveriti, ali število deli n, ter izračunati vsoto. Preverite, ali je ta vsota manjša od 2 * n ali ne.
Časovna kompleksnost tega pristopa: O ( n )
Optimizirana rešitev:
Če natančno opazujemo, so delitelji števila n prisotni v parih. Na primer, če je n = 100, so vsi pari deliteljev: (1 100) (2 50) (4 25) (5 20) (10 10)
S tem dejstvom lahko pospešimo naš program.
Pri preverjanju deliteljev bomo morali biti previdni, če obstajata dva enaka delitelja kot v primeru (10 10). V tem primeru bomo pri izračunu vsote vzeli le enega od njih.
Implementacija optimiziranega pristopa
// 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>
Izhod:
NO YES
Časovna zapletenost: O(sqrt(n))
Pomožni prostor: O(1)
Reference:
https://en.wikipedia.org/wiki/Deficient_number
