# Prime Sum | InterviewBit | Solution Explained

I explain the solution to Prime Sum, an InterviewBit question using basic mathematics. Problem Link.

## 0. Prime Sum: Problem Discussion

### 0.0. IO Format

• input
• an integer (no range given)
• output
• two prime numbers which sum to the input given
• constraints
• none given explicitly

### 0.1. Examples

For input 4, we can have the split as 2 + 2 which satisfies the condition laid out – both are primes.

Similarly for 8 we have 8 = 3 + 5 and so on.

## 1. Prime Sum: Observations & Logic

### 1.0. Intuitions

• we know that the answer is going to be a pair of prime integers
• what if we find all the primes between [1, N]
• then iterate over the array
• then check if both i (current index) and N-i are primes or not.

Since we first need to find all the prime numbers between [1, N], we can use Sieve of Eratosthenes. Then we iterate as specified above.

## 2. Prime Sum: Optimized Implementation

### 2.0. Code

```vector<int> Solution::primesum(int n) {
vector <bool> is_prime(n+1, true);
is_prime = is_prime = false;

for (int i = 2; i * i <= n; i++) {
if (!is_prime[i]) continue;

for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}

for (int i = 2; i <= n; i++) {
if (is_prime[i] && is_prime[n-i]) return {i, n-i};
}

// dummy, will never be used because of Goldbach's conjecture
return {-1, -1};
}
```

### 2.1. Complexity Analysis

• Time: `O(N.ln.ln.sqrt.N + N)` first part is to find out all the prime numbers and the second is to iterate and find the right combination
• Space: `O(N)` to store all the prime numbers [1, N].
##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

1. Srishti Chopra :July 23, 2022 at 11:29 am

2. Makarand :August 16, 2022 at 11:06 am
3. Gopal :November 14, 2022 at 5:53 pm