Strong Three-Digit Primes
National Olympiad — Municipal round
Submission name: yako.cpp
Problem summary
List three-digit primes in [A,B] whose digit sum is both a two-digit number and prime.
Input
A B.
Output
Qualifying numbers in increasing order, separated by one space; print 0 if there are none.
Constraints
99 < A ≤ B ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
150 170
Output
157
Solution analysis
- Sieve primality through 1000.
- Check every integer in the interval, keeping only three-digit primes with a prime digit sum at least 10.
Why it works
The direct tests are exactly the three defining conditions; increasing enumeration produces the required order.
Complexity: O(U log log U + B−A+1) time and O(U) memory, U=1000.
Watch out. A prime digit sum below 10 does not qualify. 1000 is not a three-digit integer.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The direct tests are exactly the three defining conditions; increasing enumeration
// produces the required order.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
vector<bool>prime(1001,true);
prime[0]=prime[1]=false;
for(int p=2;p*p<=1000;p++){
if(prime[p]){
for(int q=p*p;q<=1000;q+=p){
prime[q]=false;
}
}
}
bool any=false;
for(int x=a;x<=b&&x<=999;x++){
int s=x/100+x/10%10+x%10;
if(prime[x]&&s>=10&&prime[s]){
if(any){
cout<<' ';
}
cout<<x;
any=true;
}
}
if(!any){
cout<<0;
}
cout<<'\n';
}