Find two prime numbers with given sum
Given an even number (greater than 2 ), print two prime numbers whose sum will be equal to given number. There may be several combinations possible. Print only first such pair.
An interesting point is, a solution always exist according to Goldbach’s conjecture.
Examples :
Input: n = 74 Output: 3 71 Input : n = 1024 Output: 3 1021 Input: n = 66 Output: 5 61 Input: n = 9990 Output: 17 9973
The idea is to find all the primes less than or equal to the given number N using Sieve of Eratosthenes. Once we have an array that tells all primes, we can traverse through this array to find pair with given sum.
C++
// C++ program to find a prime number pair whose sum is // equal to given number // C++ program to print super primes less than or equal to n. #include <bits/stdc++.h> using namespace std; // Generate all prime numbers less than n. bool SieveOfEratosthenes( int n, bool isPrime[]) { // Initialize all entries of boolean array as true. A // value in isPrime[i] will finally be false if i is Not // a prime, else true bool isPrime[n+1]; isPrime[0] = isPrime[1] = false ; for ( int i = 2; i <= n; i++) isPrime[i] = true ; for ( int p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, then it is a prime if (isPrime[p] == true ) { // Update all multiples of p for ( int i = p * p; i <= n; i += p) isPrime[i] = false ; } } } // Prints a prime pair with given sum void findPrimePair( int n) { // Generating primes using Sieve bool isPrime[n + 1]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers to find first pair for ( int i = 0; i < n; i++) { if (isPrime[i] && isPrime[n - i]) { cout << i << " " << (n - i); return ; } } } // Driven program int main() { int n = 74; findPrimePair(n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to find a prime number pair whose sum is // equal to given number // C program to print super primes less than or equal to n. #include <stdio.h> #include <stdbool.h> // Generate all prime numbers less than n. bool SieveOfEratosthenes( int n, bool isPrime[]) { // Initialize all entries of boolean array as true. A // value in isPrime[i] will finally be false if i is Not // a prime, else true bool isPrime[n+1]; isPrime[0] = isPrime[1] = false ; for ( int i = 2; i <= n; i++) isPrime[i] = true ; for ( int p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, then it is a prime if (isPrime[p] == true ) { // Update all multiples of p for ( int i = p * p; i <= n; i += p) isPrime[i] = false ; } } } // Prints a prime pair with given sum void findPrimePair( int n) { // Generating primes using Sieve bool isPrime[n + 1]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers to find first // pair for ( int i = 0; i < n; i++) { if (isPrime[i] && isPrime[n - i]) { printf ( "%d %d" ,i,n-i); return ; } } } // Driven program int main() { int n = 74; findPrimePair(n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to find a prime number pair whose sum is // equal to given number // Java program to print super primes less than or equal to n. class GFG { // Generate all prime numbers less than n. static boolean SieveOfEratosthenes( int n, boolean isPrime[]) { // Initialize all entries of boolean array as true. // A value in isPrime[i] will finally be false if i // is Not a prime, else true bool isPrime[n+1]; isPrime[ 0 ] = isPrime[ 1 ] = false ; for ( int i = 2 ; i <= n; i++) isPrime[i] = true ; for ( int p = 2 ; p * p <= n; p++) { // If isPrime[p] is not changed, then it is a // prime if (isPrime[p] == true ) { // Update all multiples of p for ( int i = p * p; i <= n; i += p) isPrime[i] = false ; } } return false ; } // Prints a prime pair with given sum static void findPrimePair( int n) { // Generating primes using Sieve boolean isPrime[] = new boolean [n + 1 ]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers to find first pair for ( int i = 0 ; i < n; i++) { if (isPrime[i] && isPrime[n - i]) { System.out.print(i + " " + (n - i)); return ; } } } // Driver code public static void main(String[] args) { int n = 74 ; findPrimePair(n); } } // This code is contributed by Aditya Kumar (adityakumar129) |
Python 3
# Python 3 program to find a prime number # pair whose sum is equal to given number # Python 3 program to print super primes # less than or equal to n. # Generate all prime numbers less than n. def SieveOfEratosthenes(n, isPrime): # Initialize all entries of boolean # array as True. A value in isPrime[i] # will finally be False if i is Not a # prime, else True bool isPrime[n+1] isPrime[ 0 ] = isPrime[ 1 ] = False for i in range ( 2 , n + 1 ): isPrime[i] = True p = 2 while (p * p < = n): # If isPrime[p] is not changed, # then it is a prime if (isPrime[p] = = True ): # Update all multiples of p i = p * p while (i < = n): isPrime[i] = False i + = p p + = 1 # Prints a prime pair with given sum def findPrimePair(n): # Generating primes using Sieve isPrime = [ 0 ] * (n + 1 ) SieveOfEratosthenes(n, isPrime) # Traversing all numbers to find # first pair for i in range ( 0 , n): if (isPrime[i] and isPrime[n - i]): print (i,(n - i)) return # Driven program n = 74 findPrimePair(n) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# program to find a prime number pair whose // sum is equal to given number // C# program to print super primes less than // or equal to n. using System; class GFG { // Generate all prime numbers less than n. static bool SieveOfEratosthenes( int n, bool []isPrime) { // Initialize all entries of boolean // array as true. A value in isPrime[i] // will finally be false if i is Not a // prime, else true bool isPrime[n+1]; isPrime[0] = isPrime[1] = false ; for ( int i = 2; i <= n; i++) isPrime[i] = true ; for ( int p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true ) { // Update all multiples of p for ( int i = p * p; i <= n; i += p) isPrime[i] = false ; } } return false ; } // Prints a prime pair with given sum static void findPrimePair( int n) { // Generating primes using Sieve bool []isPrime= new bool [n + 1]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers to find first // pair for ( int i = 0; i < n; i++) { if (isPrime[i] && isPrime[n - i]) { Console.Write(i + " " + (n - i)); return ; } } } // Driver code public static void Main () { int n = 74; findPrimePair(n); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find a prime // number pair whose sum is equal // to given number // Generate all prime numbers // less than n. function SieveOfEratosthenes( $n , & $isPrime ) { // Initialize all entries of // boolean array as true. A value // in isPrime[i] will finally // be false if i is Not a prime, // else true bool isPrime[n+1]; $isPrime [0] = $isPrime [1] = false; for ( $i = 2; $i <= $n ; $i ++) $isPrime [ $i ] = true; for ( $p = 2; $p * $p <= $n ; $p ++) { // If isPrime[p] is not changed, // then it is a prime if ( $isPrime [ $p ] == true) { // Update all multiples of p for ( $i = $p * $p ; $i <= $n ; $i += $p ) $isPrime [ $i ] = false; } } } // Prints a prime pair with given sum function findPrimePair( $n ) { // Generating primes using Sieve $isPrime = array_fill (0, $n + 1, NULL); SieveOfEratosthenes( $n , $isPrime ); // Traversing all numbers // to find first pair for ( $i = 0; $i < $n ; $i ++) { if ( $isPrime [ $i ] && $isPrime [ $n - $i ]) { echo $i . " " . ( $n - $i ); return ; } } } // Driver Code $n = 74; findPrimePair( $n ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to find a prime number pair whose // sum is equal to given number // Java program to print super primes less than // or equal to n. // Generate all prime numbers less than n. function SieveOfEratosthenes(n,isPrime) { // Initialize all entries of boolean // array as true. A value in isPrime[i] // will finally be false if i is Not a // prime, else true bool isPrime[n+1]; isPrime[0] = isPrime[1] = false ; for (let i = 2; i <= n; i++) isPrime[i] = true ; for (let p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true ) { // Update all multiples of p for (let i = p * p; i <= n; i += p) isPrime[i] = false ; } } return false ; } // Prints a prime pair with given sum function findPrimePair(n) { // Generating primes using Sieve let isPrime = new Array(n+1); for (let i=0;i<n+1;i++) { isPrime[i]= false ; } SieveOfEratosthenes(n, isPrime); // Traversing all numbers to find first // pair for (let i = 0; i < n; i++) { if (isPrime[i] && isPrime[n - i]) { document.write(i + " " + (n - i)); return ; } } } // Driver code let n = 74; findPrimePair(n); // This code is contributed by rag2127 </script> |
Output:
3 71
Time complexity: O(n*log(logn))
Auxiliary Space: O(n)