Finding Prime Numbers

It's easy to write a computer program to find prime numbers. In the late 1990's, while teaching middle-school math, I wrote a program (in the Basic language) that ran on my ancient [pre-Windows] IBM laptop. Here are the principles it followed:

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. (I didn't have to check any even numbers above 2, because they are all composite.)

If 3 is not a factor of x, add two 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 two 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. 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!