Goldbach Conjecture

In the 18th century, two mathematicians came up with a conjecture - known by its original creator - named Goldbach conjecture. It says that any even number greater than 2 can be expressed as a sum of two primes. There is no theoretical proof for this yet, but it is said to hold up to 400 trillion.


A program to test Golbach conjecture for a given integer:

	def first_clear(arr, idx):
	for i in range(idx, len(arr)):
	if arr[i] == 0:
	return i
	return -1
	def find_all_primes_upto(n):
	sieve = [0] * (n+1)
	i = 2
	while i>-1:
	idx = i
	while i+idx < n+1:
	i += idx
	sieve[i] = 1
	i = first_clear(sieve, idx+1)
	return [i for i in range(2, len(sieve)) if sieve[i]==0]
	def find_two_primes_sum_to(n):
	primes = find_all_primes_upto(n)
	d = set()
	for prime in primes:
	other = n - prime
	if other in d:
	return other, prime
	else:
	d.add(prime)
	return None
	a = [100, 489932, 1000000, 6788, 234, 1290]
	for e in a:
	print (find_two_primes_sum_to(e))

view raw goldbach.py hosted with ❤ by GitHub

This program demonstrates two algorithms that are well known.

1. The sieve of Eratosthenes to calculate all primes upto a given number 
2. A linear algorithm to find if two numbers in a list sum to a given number.

To prove the Goldbach conjecture for a given n, we use the sieve to find all prime numbers up to n, then use the linear algorithm to find two primes from this list that sums up to n.