Program for Goldbach’s Conjecture (Two Primes with given Sum)
Goldbach’s conjecture is one of the oldest and best-known unsolved problems in the number theory of mathematics. Every even integer greater than 2 can be expressed as the sum of two primes.
Examples:
Input : n = 44 Output : 3 + 41 (both are primes) Input : n = 56 Output : 3 + 53 (both are primes)
Approach: 1
- Find the prime numbers using Sieve of Sundaram
- Check if the entered number is an even number greater than 2 or not, if no return.
- If yes, then one by one subtract a prime from N and then check if the difference is also a prime. If yes, then express it as a sum.
Below is the implementation of the above approach:
C++
// C++ program to implement Goldbach's conjecture #include<bits/stdc++.h> using namespace std; const int MAX = 10000; // Array to store all prime less than and equal to 10^6 vector < int > primes; // Utility function for Sieve of Sundaram void sieveSundaram() { // In general Sieve of Sundaram, produces primes smaller // than (2*x + 2) for a number given number x. Since // we want primes smaller than MAX, we reduce MAX to half // This array is used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j bool marked[MAX/2 + 100] = {0}; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for ( int i=1; i<=( sqrt (MAX)-1)/2; i++) for ( int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1) marked[j] = true ; // Since 2 is a prime number primes.push_back(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for ( int i=1; i<=MAX/2; i++) if (marked[i] == false ) primes.push_back(2*i + 1); } // Function to perform Goldbach's conjecture void findPrimes( int n) { // Return if number is not even or less than 3 if (n<=2 || n%2 != 0) { cout << "Invalid Input \n" ; return ; } // Check only upto half of number for ( int i=0 ; primes[i] <= n/2; i++) { // find difference by subtracting current prime from n int diff = n - primes[i]; // Search if the difference is also a prime number if (binary_search(primes.begin(), primes.end(), diff)) { // Express as a sum of primes cout << primes[i] << " + " << diff << " = " << n << endl; return ; } } } // Driver code int main() { // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); return 0; } |
Java
// Java program to implement Goldbach's conjecture import java.util.*; class GFG { static int MAX = 10000 ; // Array to store all prime less // than and equal to 10^6 static ArrayList<Integer> primes = new ArrayList<Integer>(); // Utility function for Sieve of Sundaram static void sieveSundaram() { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for // a number given number x. Since // we want primes smaller than MAX, // we reduce MAX to half This array is // used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j boolean [] marked = new boolean [MAX / 2 + 100 ]; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for ( int i = 1 ; i <= (Math.sqrt(MAX) - 1 ) / 2 ; i++) for ( int j = (i * (i + 1 )) << 1 ; j <= MAX / 2 ; j = j + 2 * i + 1 ) marked[j] = true ; // Since 2 is a prime number primes.add( 2 ); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for ( int i = 1 ; i <= MAX / 2 ; i++) if (marked[i] == false ) primes.add( 2 * i + 1 ); } // Function to perform Goldbach's conjecture static void findPrimes( int n) { // Return if number is not even or less than 3 if (n <= 2 || n % 2 != 0 ) { System.out.println( "Invalid Input " ); return ; } // Check only upto half of number for ( int i = 0 ; primes.get(i) <= n / 2 ; i++) { // find difference by subtracting // current prime from n int diff = n - primes.get(i); // Search if the difference is // also a prime number if (primes.contains(diff)) { // Express as a sum of primes System.out.println(primes.get(i) + " + " + diff + " = " + n); return ; } } } // Driver code public static void main (String[] args) { // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes( 4 ); findPrimes( 38 ); findPrimes( 100 ); } } // This code is contributed by mits |
Python3
# Python3 program to implement Goldbach's # conjecture import math MAX = 10000 ; # Array to store all prime less # than and equal to 10^6 primes = []; # Utility function for Sieve of Sundaram def sieveSundaram(): # In general Sieve of Sundaram, produces # primes smaller than (2*x + 2) for a # number given number x. Since we want # primes smaller than MAX, we reduce # MAX to half. This array is used to # separate numbers of the form i + j + 2*i*j # from others where 1 <= i <= j marked = [ False ] * ( int ( MAX / 2 ) + 100 ); # Main logic of Sundaram. Mark all # numbers which do not generate prime # number by doing 2*i+1 for i in range ( 1 , int ((math.sqrt( MAX ) - 1 ) / 2 ) + 1 ): for j in range ((i * (i + 1 )) << 1 , int ( MAX / 2 ) + 1 , 2 * i + 1 ): marked[j] = True ; # Since 2 is a prime number primes.append( 2 ); # Print other primes. Remaining primes # are of the form 2*i + 1 such that # marked[i] is false. for i in range ( 1 , int ( MAX / 2 ) + 1 ): if (marked[i] = = False ): primes.append( 2 * i + 1 ); # Function to perform Goldbach's conjecture def findPrimes(n): # Return if number is not even # or less than 3 if (n < = 2 or n % 2 ! = 0 ): print ( "Invalid Input" ); return ; # Check only upto half of number i = 0 ; while (primes[i] < = n / / 2 ): # find difference by subtracting # current prime from n diff = n - primes[i]; # Search if the difference is also # a prime number if diff in primes: # Express as a sum of primes print (primes[i], "+" , diff, "=" , n); return ; i + = 1 ; # Driver code # Finding all prime numbers before limit sieveSundaram(); # Express number as a sum of two primes findPrimes( 4 ); findPrimes( 38 ); findPrimes( 100 ); # This code is contributed # by chandan_jnu |
C#
// C# program to implement Goldbach's conjecture using System; using System.Collections.Generic; class GFG { static int MAX = 10000; // Array to store all prime less // than and equal to 10^6 static List< int > primes = new List< int >(); // Utility function for Sieve of Sundaram static void sieveSundaram() { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for // a number given number x. Since // we want primes smaller than MAX, // we reduce MAX to half This array is // used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j Boolean[] marked = new Boolean[MAX / 2 + 100]; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for ( int i = 1; i <= (Math.Sqrt(MAX) - 1) / 2; i++) for ( int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true ; // Since 2 is a prime number primes.Add(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for ( int i = 1; i <= MAX / 2; i++) if (marked[i] == false ) primes.Add(2 * i + 1); } // Function to perform Goldbach's conjecture static void findPrimes( int n) { // Return if number is not even or less than 3 if (n <= 2 || n % 2 != 0) { Console.WriteLine( "Invalid Input " ); return ; } // Check only upto half of number for ( int i = 0 ; primes[i] <= n / 2; i++) { // find difference by subtracting // current prime from n int diff = n - primes[i]; // Search if the difference is // also a prime number if (primes.Contains(diff)) { // Express as a sum of primes Console.WriteLine(primes[i] + " + " + diff + " = " + n); return ; } } } // Driver code public static void Main (String[] args) { // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP program to implement Goldbach's // conjecture $MAX = 10000; // Array to store all prime less than // and equal to 10^6 $primes = array (); // Utility function for Sieve of Sundaram function sieveSundaram() { global $MAX , $primes ; // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // number given number x. Since we want // primes smaller than MAX, we reduce // MAX to half. This array is used to // separate numbers of the form i + j + 2*i*j // from others where 1 <= i <= j $marked = array_fill (0, (int)( $MAX / 2) + 100, false); // Main logic of Sundaram. Mark all // numbers which do not generate prime // number by doing 2*i+1 for ( $i = 1; $i <= (sqrt( $MAX ) - 1) / 2; $i ++) for ( $j = ( $i * ( $i + 1)) << 1; $j <= $MAX / 2; $j = $j + 2 * $i + 1) $marked [ $j ] = true; // Since 2 is a prime number array_push ( $primes , 2); // Print other primes. Remaining primes // are of the form 2*i + 1 such that // marked[i] is false. for ( $i = 1; $i <= $MAX / 2; $i ++) if ( $marked [ $i ] == false) array_push ( $primes , 2 * $i + 1); } // Function to perform Goldbach's conjecture function findPrimes( $n ) { global $MAX , $primes ; // Return if number is not even // or less than 3 if ( $n <= 2 || $n % 2 != 0) { print ( "Invalid Input \n" ); return ; } // Check only upto half of number for ( $i = 0; $primes [ $i ] <= $n / 2; $i ++) { // find difference by subtracting // current prime from n $diff = $n - $primes [ $i ]; // Search if the difference is also a // prime number if (in_array( $diff , $primes )) { // Express as a sum of primes print ( $primes [ $i ] . " + " . $diff . " = " . $n . "\n" ); return ; } } } // Driver code // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); // This code is contributed by chandan_jnu ?> |
Javascript
<script> // Javascript program to implement Goldbach's // conjecture let MAX = 10000; // Array to store all prime less than // and equal to 10^6 let primes = new Array(); // Utility function for Sieve of Sundaram function sieveSundaram() { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // number given number x. Since we want // primes smaller than MAX, we reduce // MAX to half. This array is used to // separate numbers of the form i + j + 2*i*j // from others where 1 <= i <= j let marked = new Array(parseInt(MAX / 2) + 100).fill( false ); // Main logic of Sundaram. Mark all // numbers which do not generate prime // number by doing 2*i+1 for (let i = 1; i <= (Math.sqrt(MAX) - 1) / 2; i++) for (let j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true ; // Since 2 is a prime number primes.push(2); // Print other primes. Remaining primes // are of the form 2*i + 1 such that // marked[i] is false. for (let i = 1; i <= MAX / 2; i++) if (marked[i] == false ) primes.push(2 * i + 1); } // Function to perform Goldbach's conjecture function findPrimes(n) { // Return if number is not even // or less than 3 if (n <= 2 || n % 2 != 0) { document.write( "Invalid Input <br>" ); return ; } // Check only upto half of number for (let i = 0; primes[i] <= n / 2; i++) { // find difference by subtracting // current prime from n let diff = n - primes[i]; // Search if the difference is also a // prime number if (primes.includes(diff)) { // Express as a sum of primes document.write(primes[i] + " + " + diff + " = " + n + "<br>" ); return ; } } } // Driver code // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); // This code is contributed by gfgking </script> |
Output
2 + 2 = 4 7 + 31 = 38 3 + 97 = 100
Time Complexity: O(n log n)
Auxiliary Space: O(MAX)
A Goldbach number is a positive integer that can be expressed as the sum of two odd primes. Since four is the only even number greater than two that requires the even prime 2 in order to be written as the sum of two primes, another form of the statement of Goldbach’s conjecture is that all even integers greater than 4 are Goldbach numbers.