# 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[0] = is_prime[1] = 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].

### Recommended Posts

##### Water Flow | InterviewBit | Solution Explained

May 11, 2022