Prime Chains
National Olympiad — Regional round (2021 season)
Submission name: primes.cpp
Problem summary
Find a prime p in [a,b] with the longest representation as a sum of consecutive primes smaller than p. A prime with no such representation has its singleton chain. Break ties by the smaller p.
Input
The interval endpoints a and b.
Output
First p and its chain length, then the chain in increasing order. Print no prime if the interval contains no prime.
Constraints
0 < a ≤ b < 1000000.
Worked example
An independently prepared example for this explanation.
Input
10 20
Output
17 4 2 3 5 7
Solution analysis
- Use the sieve of Eratosthenes to identify all primes up to b and store them in increasing order. For each possible starting prime, extend a consecutive chain until its sum exceeds b.
- Every time the sum lies in [a,b] and is prime, compare its chain length with the best answer. A chain of length at least two automatically contains only smaller primes. Singleton chains provide the fallback for primes with no longer representation.
- For [10,20], extending from 2 gives sums 2, 5, 10, 17, 28. The prime 17 has length four and beats every shorter candidate, so the chain is 2,3,5,7. If there is no candidate at all, the interval contains no prime.
Why it works
Every consecutive prime sequence with sum at most b is visited by its unique starting position and ending position. All sums are positive, so stopping after exceeding b skips no feasible chain. The comparison retains the longest valid chain and the smallest resulting prime among ties; singleton enumeration ensures a fallback exactly when needed.
Watch out. Reset the running sum for each start. The tie is on the represented prime, and the literal failure output is no prime.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Use the sieve of Eratosthenes to identify all primes up to b and store them in
// increasing order.
using namespace std;
int main(){
int lower,upper;
cin>>lower>>upper;
vector<bool>prime(upper+1,true);
prime[0]=false;
if(upper>=1){
prime[1]=false;
}
for(int p=2;p*p<=upper;++p){
if(prime[p]){
for(int multiple=p*p;multiple<=upper;multiple+=p){
prime[multiple]=false;
}
}
}
vector<int>primes;
for(int p=2;p<=upper;++p){
if(prime[p]){
primes.push_back(p);
}
}
int bestPrime=upper+1,bestLength=0,bestStart=0;
for(int start=0;start<static_cast<int>(primes.size());++start){
int sum=0;
for(int end=start;end<static_cast<int>(primes.size());++end){
sum+=primes[end];
if(sum>upper){
break;
}
int length=end-start+1;
if(sum>=lower&&prime[sum]&&
(length>bestLength||(length==bestLength&&sum<bestPrime))){
bestPrime=sum;
bestLength=length;
bestStart=start;
}
}
}
if(bestLength==0){
cout<<"no prime\n";
return 0;
}
cout<<bestPrime<<' '<<bestLength<<'\n';
for(int i=0;i<bestLength;++i){
cout<<(i==0?"":" ")<<primes[bestStart+i];
}
cout<<'\n';
}