Given an integer ‘sum’ (less than 10^8), the task is to find a pair of prime numbers whose sum is equal to the given ‘sum’
Out of all the possible pairs, the absolute difference between the chosen pair must be minimum.
If the ‘sum’ cannot be represented as a sum of two prime numbers then print “Cannot be represented as sum of two primes”.
Examples:
Input : Sum = 1002 Output : Primes: 499 503 Explanation 1002 can be represented as sum of many prime number pairs such as 499 503 479 523 461 541 439 563 433 569 431 571 409 593 401 601... But 499 and 503 is the only pair which has minimum difference Input :Sum = 2002 Output : Primes: 983 1019
Solution
- We will create a sieve of Eratosthenes which will store all the prime numbers and check whether a number is prime or not in O(1) time.
- Now, to find two prime numbers with sum equal to the given variable, ‘sum’. We will start a loop from sum/2 to 1 (to minimize the absolute difference) and check whether the loop counter ‘i’ and ‘sum-i’ are both prime.
- If they are prime then we will print them and break out of the loop.
- If the ‘sum’ cannot be represented as a sum of two prime numbers then we will print “Cannot be represented as sum of two primes”.
Below is the implementation of the above solution:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;#define MAX 100000000// stores whether a number is prime or notbool prime[MAX + 1];// create the sieve of eratosthenesvoid SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. memset(prime, true, sizeof(prime)); prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// find the two prime numbers with minimum// difference and whose sum is equal to// variable sumvoid find_Prime(int sum){ // start from sum/2 such that // difference between i and sum-i will be // minimum for (int i = sum / 2; i > 1; i--) { // if both 'i' and 'sum - i' are prime then print // them and break the loop if (prime[i] && prime[sum - i]) { cout << i << " " << (sum - i) << endl; return; } } // if there is no prime cout << "Cannot be represented as sum of two primes" << endl;}// Driver codeint main(){ // create the sieve SieveOfEratosthenes(); int sum = 1002; // find the primes find_Prime(sum); return 0;} |
Java
//Java implementation of the above approach class GFG { static final int MAX = 100000000; // stores whether a number is prime or not static boolean prime[] = new boolean[MAX + 1]; // create the sieve of eratosthenes static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. for (int i = 0; i < prime.length; i++) { prime[i] = true; } prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (int i = p * 2; i <= MAX; i += p) { prime[i] = false; } } } } // find the two prime numbers with minimum // difference and whose sum is equal to // variable sum static void find_Prime(int sum) { // start from sum/2 such that // difference between i and sum-i will be // minimum for (int i = sum / 2; i > 1; i--) { // if both 'i' and 'sum - i' are prime then print // them and break the loop if (prime[i] && prime[sum - i]) { System.out.println(i + " " + (sum - i)); return; } } // if there is no prime System.out.println("Cannot be represented as sum of two primes"); } public static void main(String []args) { // create the sieve SieveOfEratosthenes(); int sum = 1002; // find the primes find_Prime(sum); }}/*This code is contributed by 29AjayKumar*/ |
Python3
# Python 3 implementation of the above approachfrom math import sqrt# stores whether a number is prime or not# create the sieve of eratosthenesdef SieveOfEratosthenes(): MAX = 1000001 # Create a boolean array "prime[0..n]" and # initialize all entries it as true. A value # in prime[i] will finally be false if i is # Not a prime, else true. prime = [True for i in range(MAX + 1)] prime[1] = False for p in range(2, int(sqrt(MAX)) + 1, 1): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p # as non-prime for i in range(p * 2, MAX + 1, p): prime[i] = False return prime # find the two prime numbers with minimum# difference and whose sum is equal to# variable sumdef find_Prime(sum): # start from sum/2 such that difference # between i and sum-i will be minimum # create the sieve prime = SieveOfEratosthenes() i = int(sum / 2) while(i > 1): # if both 'i' and 'sum - i' are prime # then print them and break the loop if (prime[i] and prime[sum - i]): print(i, (sum - i)) return i -= 1 # if there is no prime print("Cannot be represented as sum", "of two primes")# Driver codeif __name__ == '__main__': sum = 1002 # find the primes find_Prime(sum)# This code is contributed by# Shashank_Sharma |
C#
// C# implementation of the // above approach class GFG {static int MAX = 1000000;// stores whether a number is// prime or not static bool[] prime = new bool[MAX + 1];// create the sieve of eratosthenes static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. for (int i = 0; i < prime.Length; i++) { prime[i] = true; } prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p // as non-prime for (int i = p * 2; i <= MAX; i += p) { prime[i] = false; } } }}// find the two prime numbers with // minimum difference and whose sum // is equal to variable sum static void find_Prime(int sum) { // start from sum/2 such that // difference between i and sum-i // will be minimum for (int i = sum / 2; i > 1; i--) { // if both 'i' and 'sum - i' // are prime then print // them and break the loop if (prime[i] && prime[sum - i]) { System.Console.WriteLine(i + " " + (sum - i)); return; } } // if there is no prime System.Console.WriteLine("Cannot be represented " + "as sum of two primes");}// Driver Codestatic void Main() { // create the sieve SieveOfEratosthenes(); int sum = 1002; // find the primes find_Prime(sum);}}// This code is contributed by mits |
Javascript
<script>// Javascript implementation of the above approachvar MAX = 1000001;// stores whether a number is prime or notvar prime = Array(MAX+1).fill(true);// create the sieve of eratosthenesfunction SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. prime[1] = false; for (var p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (var i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// find the two prime numbers with minimum// difference and whose sum is equal to// variable sumfunction find_Prime(sum){ // start from sum/2 such that // difference between i and sum-i will be // minimum for (var i = parseInt(sum / 2); i > 1; i--) { // if both 'i' and 'sum - i' are prime then print // them and break the loop if (prime[i] && prime[sum - i]) { document.write( i + " " + (sum - i) + "<br>"); return; } } // if there is no prime document.write( "Cannot be represented as sum of two primes" + "<br>");}// Driver code// create the sieveSieveOfEratosthenes();var sum = 1002;// find the primesfind_Prime(sum);</script> |
Output:
499 503
Time Complexity: O(n + MAX3/2)
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
