Problem

Submissions

Hints & solutions

Discuss

Pair Of Primes

Moderate

0/80

Average time to solve is 15m

Contributed by

7 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

Correct
Correct
Correct

Explanation to Sample Input 1 :

In the first test case, there is only one pair of prime numbers that sums up to 4 that is ( 2, 2).

In the second test case, there is only one pair of prime numbers that sums up to 6 that is ( 3, 3).

In the third test case, there is only one pair of prime numbers that sums up to 8 that is ( 3, 5).

Sample Input 2 :

Sample Output 2 :

Correct
Correct
Correct

Explanation to Sample Input 2 :

In the first test case, there is only one pair of prime numbers that sums up to 12 that is ( 5, 7).

In the second test case, there are two pairs of prime numbers that sums up to 14 that are ( 3, 11) and ( 7, 7) but the first pair has the smallest prime number that is 3.

In the second test case, there are two pairs of prime numbers that sums up to 16 that are ( 3, 13) and ( 5, 11) but the first pair has the smallest prime number that is 3.

Hint 1

Hint 2

Bruteforce

Try to cover all possible pairs of prime.

Approaches (2)

Approach 1

Approach 2

Bruteforce

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

Time Complexity

O(K*log(log(K)) + N^2), where K is the given sum and N is the number of primes less than K.

The complexity of K*log(log(K)) is due to the Sieve of Eratosthenes and N^2 is for iterating through all pair of prime numbers. Hence, the overall time complexity is O(K*log(log(K)) + N^2).

Space Complexity

O(N), where N is the number of primes less than K.

This is the space required to store N prime numbers. Hence, the overall space complexity is O(N).

(100% EXP penalty)

Pair Of Primes

Console