Prime Sum Interviewbit Solution

Problem: Prime Sum

Problem Description:

Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number.

NOTE: A solution will always exist.

Example:

 Input : 4 
 Output: 2 + 2 = 4  

If there are more than one solutions possible, return the lexicographically smaller solution.

If [a, b] is one solution with a <= b, 
and [c,d] is another solution with c <= d, then  

[a, b] < [c, d]   

If a < c OR a==c AND b < d. 

Solution:

vector<int> Solution::primesum(int A) {
    bool vis[A+1];
    memset(vis,false,sizeof(vis));
    for(int i=2;i*i<=A;i++){
        if(!vis[i]){
            for(int j=2;i*j<A;j++){
                vis[i*j]=true;
            }
        }
    }
    vector<int>res;
    
    for(int i=2;i<=A/2;i++){
        if(!vis[A-i]&&!vis[i]){
            res.push_back(i);
            res.push_back(A-i);
            break;
        }
    }
    return res;
}