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 :

To check Prime number
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

Special thanks to Shreyas Vishwakarma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article