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;
 }