Two Primes
National Olympiad — Regional round
Submission name: twop.cpp
Problem summary
For each supplied positive integer, count its representations x+y with prime x≤y. Report the largest count among all supplied integers.
Input
The number of integers, followed by those integers.
Output
The maximum number of unordered prime-sum representations.
Constraints
At most 1000 integers, each positive and less than 5,000,000.
Worked example
An independently prepared example for this explanation.
Input
3 4 9 12
Output
1
Solution analysis
- Sieve primes through the largest input.
- For each value s, try prime x≤s/2 and test whether s−x is prime. Cache repeated values.
- Take the maximum of the counts.
Why it works
Every unordered representation has exactly one smaller member x≤s/2; the loop tests it once and only accepts a prime complement.
Complexity: O(M log log M + U·π(M/2)) time and O(M+U) space, with maximum value M and U distinct inputs.
Watch out. Count equal-prime pairs once. Odd sums can only use prime 2.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>a(n);
int M=0;
for(int&x:a){
cin>>x;
M=max(M,x);
}
vector<bool>p(M+1,true);
p[0]=false;
if(M>=1){
p[1]=false;
}
for(int i=2;i*1LL*i<=M;i++){
if(p[i]){
for(int j=i*i;j<=M;j+=i){
p[j]=false;
}
}
}
vector<int>pr;
for(int i=2;i<=M;i++){
if(p[i]){
pr.push_back(i);
}
}
unordered_map<int,int>memo;
int ans=0;
for(int s:a){
if(!memo.count(s)){
int cnt=0;
// Fix the smaller prime, so order does not create duplicates.
for(int x:pr){
if(x>s/2){
break;
}
if(p[s-x]){
cnt++;
}
}
memo[s]=cnt;
}
ans=max(ans,memo[s]);
}
cout<<ans<<'\n';
}