.
.

Goldbach's Primes - Searching

  Download Source Code

/****************************************
Matt is obsessed with math.  He heard about Goldbach's 
conjecture, which says that every even number can be
written as the sum of two prime numbers.  For example:
100 = 11 + 89 .  But it's difficult to find the primes
for a large number like a million.  Matt wrote this program
that makes a list of prime numbers up to 1 million,
and then uses the list to solve Golbach for large numbers.
*****************************************/
public class Primes
{
  int[] primes = new int[1000000];  // defaults to all zeroes
  
  public Primes()
  {
    calculatePrimes(); 
    int num = 0;
    do
    {
      num = Integer.parseInt(input("Type a large even number"));
      searchForPrimes(num); 
    } while(num != 0);      // input 0 to end the program
  }
  
  void calculatePrimes()     // sieve of Eratosthenes
  {
    primes[0] = 1;
    primes[1] = 1;
    for(int n = 2; n < 1000000; n = n+1)
    {
      int c = 2*n;
      while(c < 1000000)
      {
        primes[c] = 1;   // 1 indicates NOT prime
        c=c+n;
      } 
    } 
  }
  
  void searchForPrimes(int num)
  {
    for(int x=3; x < num; x = x+2)
    {
      int p = num - x;
      if( primes[x] == 0 && primes[p] == 0)
      {
        System.out.println(num + " = " + x + " + " + p); 
      }
    }
  }
  
  public static void main(String[] args)
  {  new Primes();  }
  
  public String input(String prompt)
  { return javax.swing.JOptionPane.showInputDialog(null,prompt); }
  
  public void output(String message)
  {  javax.swing.JOptionPane.showMessageDialog(null,message);  }
}

Computational Thinking

Computational Thinking is about analyzing problems in such a way that they can be solved by a computer system,
or at least a program can be written that will HELP to solve the problem.  Numerical problems were traditionally solved
with pencil and paper, using mathematical techniques like algebra and calculus.  But mastering mathematics is quite
difficult and most people have not learned mathematics in sufficient depth that they can use it reliably to solve problems.
There are many theorems in mathematics that might help, but most people are not aware of these theorems,
or they simply don't understand them.  And when we get to BIG math problems, even good mathematicians
encounter their own limitations.

Prime numbers are relatively easy to understand.  A prime number is one that has no factors, nothing that divides
it evenly, except 1 and itself.  For example, 83 is a prime number, but 87 is not prime because 3 divides it.
It's not so bad when we work with numbers below 100.  But what is the largest prime number smaller than 1 million?
We can start counting backward:
    999999  is divisible by 9
    999998  is not prime because it's even
    999997  is divisible by 757 - that's not so obvious, but you can try it with a calculator
    999995  is divisible by 5
    999993  is divisible by 3 because the sum of the digits is divisible by 3
    999991  is divisible by 17
    ...

This problem is quite difficult to solve.  Simply using a calculator and trying lots of numbers - 3,5,7,...757 - is far to slow.
Doing this for every number from 999999 down until a prime is found is far too time consuming.

If we write a computer program that tries one number after another, it might also take relatively long.
(Actually this doesn't take too long using a modern PC at 2 GigaHertz.)  The question arises whether there
is a faster way - e.g. a faster algorithm?

Amazingly, a Greek mathematician named Eratosthenes invented a very efficient algorithm 2000 years before the first
computer was ever built.  Algorithms before computers?  Yes indeed.  Actually, efficient algorithms were even more
important when we were doing math with pencil and paper.  With fast computers, it's easy to settle for a mediocre
algorithm because it is still fast enough.  But that is not the case with every problem - some problems are fundamentally
difficult and just don't have a fast algorithm at all, for example the Traveling Salesman Problem.

The program above uses Erastosthenes' algorithm.  It has a an array with 1 million cells.  It starts by filling the array
with 0 (zero) entries - this is automatic whenever we create an int array.  Then a loop counts through all the positions
in the array and places a 1 in every even position (except it leaves 2 blank because it is the first even number).
Next it goes through every 3rd position, storing a 1 in each cell (except position 3 which is the first one).
Now it marks every 5th position, every 7th position, etc.    This might sound slow, but it takes approximately
500,000 passes (actually less) and each pass only examines 1000000/n positions.  This is approximately
12,000,000 iterations.  That sounds like a lot of work, but the computer is running at over 2 BILLION operations
per second.  Even though each iteration takes several machine cycles, this Sieve of Eratosthenes finishes
in about 1 second.  Then the primes[ ] array contains a complete list of all the primes under 1 million.
If primes[x] contains a 0 (zero), then x is prime.

This program is actually used to answer a related question.  Goldbach's Conjecture (it has not been proven) says
that every even number can be written as the sum of 2 prime numbers.  For example,  100 = 11 + 89.
The program inputs an even number, then searches for two primes in the list that add up to that number.
That's pretty easy - start at 3, then check whether num-3 is prime.  Then try 5 and check whether num-5 is prime.
Continue until a solution is found.

Programming Practice