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].
Avatar for Tanishq Chaudhary

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

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.