Last Updated: 30 Dec, 2020
Pair Of Primes
Moderate
Asked in companies
Given a positive even integer 'K', your task is to find two prime numbers whose sum is equal to 'K'. If there are multiple answers, you may find any.
Example , for K = 4 the pair is ( 2, 2) , For K = 10 the pair is ( 3, 7).
Note :
It is guaranteed that 'K' will always be greater than two.
Input Format :
The first line of the input contains a single positive integer 'T', denoting the number of test cases.
The first and the only line of each test case contains a single positive even integer 'K', as described in the problem statement.
Output Format :
For each test case return the pair of primes whose sum is equal to 'K'.
Print the output of each test case in a separate line
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
If your output is correct our system will print “Correct”, otherwise “Incorrect”.
Constraints :
1 <= T <= 100
4 <= K <= 7000
'K' is even.
Where 'T' denotes the number of test cases and 'K' denotes the positive even integer.
Time Limit: 1 sec
Approaches
- First we will get all the prime numbers up to K using the Sieve of Eratosthenes and we will store it in the array Primes.
- Now iterate through all possible pairs of prime numbers and see if any of the pair sums up to K.
- To do this we will iterate through the array of prime numbers. Let's say we are currently at ith position , if we can find any position j such that Primes[i] + Primes[j] = K then we will return ( Primes[i], Primes[j] ).
- First we will get all the prime numbers up to K using the Sieve of Eratosthenes and we will store it in the array Primes and we will also store it in a hash map Hash.
- Now iterate through all the prime numbers.
- Lets we are currently at ith position then we will see if the number (K - Primes[i]) is also a prime.
- To do this we will use the help of Hash. If the number ( K - Primes[i]) is in the Hash then we will return the pair ( Primes[i] , K - Primes[i])