Is the Number Abundant?
National Olympiad — National round (2022 season)
Submission name: abundant.cpp
Problem summary
A number is abundant when the sum of its positive divisors excluding itself exceeds the number. Compute this proper-divisor sum and decide whether the input is abundant.
Input
One integer N.
Output
The proper-divisor sum on the first line, then YES if it exceeds N, otherwise NO.
Constraints
2 ≤ N ≤ 10¹⁴.
Worked example
An independently prepared example for this explanation.
Input
2020
Output
2264 YES
Solution analysis
- Factor N into prime powers. For a factor p^e, the possible contributions of that prime to a divisor are 1,p,…,p^e, whose sum is a geometric series.
- Multiply these prime-power sums to obtain the sum of all divisors, then subtract N to exclude the number itself. Trial division only needs to continue while divisor² does not exceed the remaining factor.
- For 2020 = 2²·5·101, the all-divisor sum is (1+2+4)(1+5)(1+101) = 4284. Removing 2020 leaves 2264, which is larger than 2020, so the answer is YES.
Why it works
Every positive divisor has a unique exponent choice for each prime factor. Expanding the product of geometric sums lists each divisor once, so its value is the exact all-divisor sum. Subtracting N gives the proper-divisor sum, and its comparison with N is the definition of abundance.
Watch out. Do not include N in the reported sum. Perfect numbers such as 6 are not abundant because equality is insufficient. A leftover factor greater than 1 is prime.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long remaining = n;
long long divisorSum = 1;
for (long long prime = 2; prime <= remaining / prime; prime++) {
if (remaining % prime != 0) {
continue;
}
long long power = 1;
long long factorSum = 1;
while (remaining % prime == 0) {
remaining /= prime;
power *= prime;
factorSum += power;
}
// Independent prime-power choices multiply to the all-divisor sum.
divisorSum *= factorSum;
}
if (remaining > 1) {
divisorSum *= remaining + 1;
}
long long properSum = divisorSum - n;
cout << properSum << '\n';
cout << (properSum > n ? "YES" : "NO") << '\n';
}