Two Prime Summands
National Olympiad — Municipal round (2012 season)
Submission name: ssum.cpp
Problem summary
Count unordered representations of x as the sum of two primes. Equal summands are allowed.
Input
One integer x.
Output
The number of prime pairs; zero if none exist.
Constraints
4 ≤ x ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
10
Output
2
Solution analysis
- Build a sieve of primes up to x. Mark 0 and 1 as nonprime and cross out multiples of every remaining prime p, starting from p².
- For each p from 2 through floor(x/2), test whether both p and x−p are prime. Restricting p to the smaller summand counts unordered pairs exactly once.
- For x=10, the valid pairs are 3+7 and 5+5, hence 2. For x=4, 2+2 is counted once; for x=11 no pair exists.
Why it works
The sieve correctly identifies all primes up to x by eliminating composites through a prime divisor. Every unordered representation has a unique smaller summand p≤x/2 and is tested exactly once.
Complexity: O(x log log x) time for the sieve plus O(x) counting; O(x) space.
Watch out. Include the equal-summand case. The number 1 is not prime.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Build a sieve of primes up to x.
using namespace std;
int main(){
int value;
cin>>value;
vector<bool>prime(value+1,true);
prime[0]=false;
prime[1]=false;
for(int p=2;p*p<=value;p++){
if(prime[p]){
for(int multiple=p*p;multiple<=value;multiple+=p){
prime[multiple]=false;
}
}
}
int answer=0;
for(int p=2;p<=value/2;p++){
if(prime[p]&&prime[value-p]){
answer++;
}
}
cout<<answer<<'\n';
}