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
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this