Program for Goldbachâ €™ s Conjecture ( Two Primes with given Sum ) | Python3 program to implement Goldbach 's conjecture ; Array to store all prime less than and equal to 10 ^ 6 ; Utility function for Sieve of Sundaram ; 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 ; Main logic of Sundaram . Mark all numbers which do not generate prime number by doing 2 * i + 1 ; Since 2 is a prime number ; Print other primes . Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; Function to perform Goldbach 's conjecture ; Return if number is not even or less than 3 ; Check only upto half of number ; find difference by subtracting current prime from n ; Search if the difference is also a prime number ; Express as a sum of primes ; Finding all prime numbers before limit ; Express number as a sum of two primes
import math NEW_LINE MAX = 10000 ; NEW_LINE primes = [ ] ; NEW_LINE def sieveSundaram ( ) : NEW_LINE INDENT marked = [ False ] * ( int ( MAX / 2 ) + 100 ) ; NEW_LINE for i in range ( 1 , int ( ( math . sqrt ( MAX ) - 1 ) / 2 ) + 1 ) : NEW_LINE INDENT for j in range ( ( i * ( i + 1 ) ) << 1 , int ( MAX / 2 ) + 1 , 2 * i + 1 ) : NEW_LINE INDENT marked [ j ] = True ; NEW_LINE DEDENT DEDENT primes . append ( 2 ) ; NEW_LINE for i in range ( 1 , int ( MAX / 2 ) + 1 ) : NEW_LINE INDENT if ( marked [ i ] == False ) : NEW_LINE INDENT primes . append ( 2 * i + 1 ) ; NEW_LINE DEDENT DEDENT DEDENT def findPrimes ( n ) : NEW_LINE INDENT if ( n <= 2 or n % 2 != 0 ) : NEW_LINE INDENT print ( " Invalid ▁ Input " ) ; NEW_LINE return ; NEW_LINE DEDENT i = 0 ; NEW_LINE while ( primes [ i ] <= n // 2 ) : NEW_LINE INDENT diff = n - primes [ i ] ; NEW_LINE if diff in primes : NEW_LINE INDENT print ( primes [ i ] , " + " , diff , " = " , n ) ; NEW_LINE return ; NEW_LINE DEDENT i += 1 ; NEW_LINE DEDENT DEDENT sieveSundaram ( ) ; NEW_LINE findPrimes ( 4 ) ; NEW_LINE findPrimes ( 38 ) ; NEW_LINE findPrimes ( 100 ) ; NEW_LINE