Express given number as Sum of Two Prime Numbers

Problem: Given a number n, express the number as a sum of 2 prime numbers.

Examples:

```Example 1:
Input : N = 74
Output : True .
Explanation: 74 can be expressed as 71 + 3 and both are prime numbers.

Example 2:
Input : N = 11
Output : False.
Explanation: 11 cannot be expressed as sum of two prime numbers.```

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Intuition:

-> We know that prime numbers are always Odd. So a prime number (odd) cannot be written as the sum of 2 odd prime numbers. So either of them has to be 2.

-> Now our question boils down to checking whether n-2 && n prime or not. If both hold true return Yes or No

Approach:

->  We will create 2 functions :

1. To check Prime number
2. To check whether both N and N-2 are prime or not

-> In checking the Prime Function, we will run a loop from i =2  to sqrt(n). If n % i is equal to 0, that means i  is divisible by n, so it’s not a prime number we will return false.

-> Same above can be done for n-2.

Code:

C++ Code

``````#include<bits/stdc++.h>
using namespace std;

class SumOf2Prime {

public:

bool isPrime(int n) {

if (n <= 1) {
return 0 ;
}

for (int i = 2; i * i <= n; i++) {
if (n % i == 0 ) {
return 0 ;
}
}

return 1;
}

bool prime(int n) {

if (isPrime(n) && isPrime(n - 2)) {
return 1;
}
else {
return 0 ;
}
}

} ;
int main() {

int n = 19 ;
SumOf2Prime s1 ;
if (s1.prime(n)) {
cout << "Yes\n"  ;
}
else {
cout << "No\n" ;
}
return 0 ;
}
``````

Output: Yes

Time Complexity: O(sqrt(n))

Reason : We are testing divisors i, 2<=i<=sqrt(n)

Space Complexity: O(1)

Reason : We are just returning boolean value

Java Code

``````import java.util.*;

public class Solution {

static boolean prime(int n) {

if (n <= 1)
return false;

for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}

return true;
}

static boolean isPrime(int n) {

if (prime(n) && prime(n - 2)) {
return true;
} else {
return false;
}
}

public static void main(String[] args) {

int n = 19;

if (isPrime(n)) {
System.out.println("Yes");
} else if (isPrime(n)) {
System.out.println("No");
}
}
}
``````

Output: Yes

Time Complexity: O(sqrt(n))

Reason : We are testing divisors i, 2<=i<=sqrt(n)

Space Complexity: O(1)

Reason : We are just returning boolean value