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].

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.