Return Two Prime Numbers Whose Sum Will Be Equal To A Number

Prashant | Sat, 13 Jun, 2020 | 930

Return two prime numbers whose sum is equal to given number

Here we will see a program to return two prime numbers such that their sum is equal to a given number, and in each case that is possible.

So how can we solve it ?

Well there are lot of solutions to this questions, but we will do it using the best optimal solution.

Question :- 

Given an even number (greater than 2), return two prime numbers whose sum will be equal to given number. There are several combinations possible. Print only first such pair. 

NOTE: A solution will always exist, read Goldbach’s conjecture. Also, solve the problem in linear time complexity, i.e., O(n).

Input:
The first line contains T, the number of test cases. The following T lines consist of a number each, for which we'll find two prime numbers.

Note: The number would always be an even number.

Output:
For every test case print two prime numbers space separated, such that the smaller number appears first. Answer for each test case must be in a new line.

Constraints:
1 ≤ T ≤ 70
2 < N ≤ 10000

Example:
Input:
5
74
1024
66 
8
9990

Output:
3 71
3 1021
5 61
3 5
17 9973

Best optimal solution :- 

#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){
    if(n<2)return 0;
    if(n%2 == 0)return 0;
    if(n == 2)return 1;
    for(int i=3;i*i<=n;i+=2) {
        if(n%i == 0) {
            return 0;
        }
    }
    return 1;
}
int main() {
	int n,num;
	cin>>n;
	while(n--) {
	    cin>>num;
	    for(int i=2;i<=num/2;i++) {
	        if(isprime(i) && isprime(num-i)) {
	            cout<<i<<" "<<num-i<<endl;
	            break;
	        }
	    }
	}
	return 0;
}
Correct Answer
Execution Time:0.01.

0 comments
Leave a comment