C++ Program To Check If a Prime Number Can Be Expressed as Sum of Two Prime Numbers
Given a prime number . The task is to check if it is possible to express as sum of two separate prime numbers.
Note: The range of N is less than 108.
Examples:
Input: N = 13 Output: Yes Explanation: The number 13 can be written as 11 + 2, here 11 and 2 are both prime. Input: N = 11 Output: No
Simple Solution: A simple solution is to create a sieve to store all the prime numbers less than the number N. Then run a loop from 1 to N and check whether and are both prime or not. If yes then print Yes, else No.
Efficient solution: Apart from 2, all of the prime numbers are odd. So it is not possible to represent a prime number (which is odd) to be written as a sum of two odd prime numbers, so we are sure that one of the two prime number should be 2. So we have to check whether n-2 is prime or not. If it holds we print Yes else No.
For example, if the number is 19 then we have to check whether 19-2 = 17 is a prime number or not. If 17 is a prime number then print yes otherwise print no.
Below is the implementation of the above approach:
C++
// C++ program to check if a prime number // can be expressed as sum of // two Prime Numbers #include <bits/stdc++.h> using namespace std; // Function to check whether // a number is prime or not bool isPrime( int n) { if (n <= 1) return false ; for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) return false ; } return true ; } // Function to check if a prime number // can be expressed as sum of // two Prime Numbers bool isPossible( int N) { // if the number is prime, // and number-2 is also prime if (isPrime(N) && isPrime(N - 2)) return true ; else return false ; } // Driver code int main() { int n = 13; if (isPossible(n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Yes
Contact Us