Sadly, or perhaps happily for internet security, there is no explicit formula that will generate the prime numbers. Many students have heard about Euler's interesting formula n2 + n + 41 which will generate 40 consecutive prime numbers when n=0 to 39 are entered. The first few are 41, 43, 47, 53, 61... (I think I remember reading that there is no polynomial that will produce a longer string of primes for consecutive arguments) but if you want to find ALL the primes, some form of sieve is required.
Sieve is not a well known word to many students. They are more likely to know the kitchen implement as a sifter. The two synonymous nouns describe a tool which, in the words of one dictionary, "separates wanted elements from unwanted material using a filter such as a mesh or net. " A prime sieve then, separates out primes from non-primes. Most students encounter the sieve of Eratosthenes in middle school. You take a list of integers and circle two, and then cross off every 2nd number after that as multiples of two, then circle three and cross out every third number (some of which will be already crossed out). Each time you return to the beginning of the list, you circle the next unmarked number n, and then crossing out every nth number following.
Around 1930, a little known or remembered Indian mathematician named S.P. Sundaram came up with a different sieve. It operates on simple arithmetic sequences.
Start with 4 and create an arithmetic sequence by repeatedly adding three... 4, 7, 10, 13, 16, 19, 22...
In the second row, start with seven, and add five each time 7, 12, 17, 22, 27,....
continue starting with each number in the first sequence as the initial term, and to each sequence add the next consecutive odd number...
It looks like this
4 7 10 13 16 19 22 25 28
7 12 17 22 27 32 37 42 47
10 17 24 31 38 45 52 59 66
13 22 31 40 49 58 67 76 85
16 27 38 49 60 71 82 93 104
Ok, some are prime, some are not....what's up.... Take any number that appears in the list, multiply by two and add one.... Now check, Is it prime??
Try another... and time after time it turns out the number is NOT prime. 17 is in the numbers, and 2(17)+1 = 35, which is not prime...
But now find a number that does not show up in the list... five is not there, neither is six, or eight, or lots of others. Repeat the 2n+1 idea and Voila..primes emerge.
Cute, but the most intriguing sieve I have ever seen is called the visual sieve, and uses a parabola and a straight edge. Start with the simple parabola x=y2 and label the point for each integral point, (1,1); (4,2) etc... with the absolute value of its y-coordinate.. It will look sort of like this. Now connect the point at (4,2) with all the points below the x-axis. You should get something that looks like this:
Notice that each point on the x-axis that is crossed out is a composite number. Repeat for every number above the x-axis and you will eventually get something that looks like this,
it actually looks a little like a sieve. Notice that we are left with only the prime numbers on the x-axis.
I came across this on the Plus Math web magazine article "Catching primes" by Abigail Kirk. Even better for students, they have a really nice section called "Why does that work?" They are also the source of all the colorful pictures I just used, and actually they have several more that make it even easier for a student to follow... pass this on to your students.