The Smallest Prime Prize
National Olympiad — National round (2015 season)
Submission name: quiz.cpp
Problem summary
Append at least one decimal digit to the right of n so that the result is prime. Find the smallest possible resulting prime.
Input
An integer n.
Output
The smallest prime having the decimal representation of n as a proper prefix.
Constraints
1 ≤ n ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
12
Output
127
Solution analysis
- Appending exactly d digits produces precisely the interval [n × 10^d, (n + 1) × 10^d − 1]. Leading zeros in the appended suffix are allowed, so every number in that interval is a candidate.
- Try suffix lengths starting at one and scan each interval in increasing order. Test primality by trial division up to the square root, treating values below 2 as nonprime. Stop at the first prime.
- For prefix 12 the first interval is 120…129. Values 120 through 126 are composite, while 127 is prime, so 127 is the answer. Prefix 41 similarly gives 419.
Why it works
Within each interval the scan returns its smallest prime. Every number in a shorter suffix-length interval has fewer decimal digits and is smaller than every number in a longer interval. Thus the first prime found across the ordered intervals is the smallest allowed result.
Watch out. At least one digit must be appended, even if n is already prime. If no one-digit suffix works, continue to longer suffixes. Use divisor ≤ value/divisor to avoid squaring overflow.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
bool isPrime(long long value) {
if (value < 2) {
return false;
}
if (value % 2 == 0) {
return value == 2;
}
for (long long divisor = 3; divisor <= value / divisor; divisor += 2) {
if (value % divisor == 0) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
long long scale = 10;
while (true) {
// A suffix of this length fills exactly this contiguous numeric interval.
long long low = n * scale;
long long high = (n + 1) * scale - 1;
for (long long value = low; value <= high; ++value) {
if (isPrime(value)) {
cout << value << '\n';
return 0;
}
}
scale *= 10;
}
return 0;
}