Friday, April 20, 2018

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:

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.

No comments: