Guess from a Prime Divisor Sum
National Olympiad — National round (2025 season)
Submission name: guess.cpp
Problem summary
A positive integer X has a prime divisor P. Given S=X+P, find every possible X. Answers may appear in any order.
Input
One integer S.
Output
All possible positive X values separated by spaces.
Constraints
1 ≤ S ≤ 10^14; at least one valid X exists.
Worked example
An independently prepared example for this explanation.
Input
20
Output
18 15
Solution analysis
- Because P divides X and S=X+P, P also divides S. Conversely, any prime divisor P of S with P<S gives X=S−P>0 and P divides X.
- Factor S and retain each distinct prime factor once. For each factor, print S−P. Trial division up to the square root of the remaining value suffices; removing repeated factors avoids duplicate answers.
- For S=20, the distinct prime divisors are 2 and 5, producing X=18 and X=15. For S=32, the only prime divisor is 2, giving X=30.
Why it works
The divisibility equivalence proves a one-to-one correspondence between valid prime choices and distinct proper prime divisors of S. Complete factorization finds all and only these choices, and different primes produce different X.
Watch out. Remove every power of a found factor before continuing. Do not print once per repeated factor. Use long long for S and loop comparisons.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
long long sum;
cin >> sum;
long long remaining = sum;
vector<long long> factors;
// Prime divisors of S are exactly the possible prime divisors P of X=S-P.
for (long long factor = 2; factor <= remaining / factor; factor += factor == 2 ? 1 : 2) {
if (remaining % factor == 0) {
factors.push_back(factor);
while (remaining % factor == 0) {
remaining /= factor;
}
}
}
if (remaining > 1) {
factors.push_back(remaining);
}
bool first = true;
for (long long factor : factors) {
if (factor < sum) {
if (!first) {
cout << ' ';
}
first = false;
cout << sum - factor;
}
}
cout << '\n';
}