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.
*****************************************/
int[] primes = new int[1000000]; // defaults to all zeroes
void setup()
{
calculatePrimes();
int num = 0;
do
{
num = int(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) // find two primes that add up to NUM
{
for(int x=3; x < num; x = x+2)
{
int p = num - x;
if( primes[x] == 0 && primes[p] == 0)
{
println(num + " = " + x + " + " + p);
}
}
}
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
- Download the program, run it and try a few even numbers.
Make sure it works sensibly.
- Change the program so that it asks for a number and simply
tells whether that number is prime.
Use your program to find the largest prime number under 1
million.
- Another puzzle is called "twin primes" - those are two odd
numbers, one right after the other,
where both are primes. For example, 17 and 19 are twin
primes, as well as 101 and 103.
Write a method that loops through the primes array, looking at
all the ODD position (start at 3)
checking whether primes[x] and primes[x+2] are both equal to 0.
- Try to change the program to do more primes - make the array
bigger and have it count longer.
Can it do 10 million? 100 milllion? Is there a
limit?
- Now use your program to solve the most common prime number
problem -
given a large number, like 999997, search for a prime number
that divides the number.
Write a method to solve this problem, at least up to 1 million.