Finding
Prime Numbers
It's easy to write a computer program to find prime numbers. In the late 1990's, while teaching
middleschool math, I wrote a program (in the Basic language) that ran on my ancient [preWindows] IBM laptop. It
followed this process:
*Take an odd number (call it x). For example, if you already know the prime
numbers up to 10, you can start with x = 11. (We don't have to test even numbers, since every even number
greater than 2 is composite, with at least three factors [1, 2, and itself].)
*Find out whether 3 is a factor of x, by seeing whether (x/3) is an
integer. If 3 is a factor of x, then start testing the next odd number, x+2, to see if
it is prime.
*If 3 is not a factor of x, add 2 to it and try again: that is, see
whether 5 is a factor of x. (Since all of my possible prime numbers above 2 were odd, I didn't have
to test whether even numbers were factors of those odd numbers; the answer would always be
no.)
Keep adding 2 to the possible factor until it gets larger than the square root of
x. If none of those numbers is a factor of x, then put x onto the list of prime
numbers.
Add 2 to x, and start the process over.
To find Mersenne primes, of course, you would need to tell your program to check only Mersenne
numbers. For each prime number x, you would have the program test 2^{x} – 1 to
see whether it is prime.
Improving the
process
My program was very inefficient. A better one would
only use prime numbers as potential factors of x. You don't have to check composite numbers, because
their factors would already have been factors of x. (For instance, if 5 doesn't go into a
number, then you know that 15 won't go into it either.)
I didn't know how to store a list of numbers that the
program had identified as prime so that I could use them as potential factors when testing other numbers. If
you know more than a little programming, you can write a better program than I did!
