This is Math Newsletter number 8; Wednesday, September 15, 2010.
If you send any part of this newsletter to a friend, please
also include this paragraph. To subscribe or unsubscribe,
send a personal email request to kermit@polaris.net
Archive is at

Using Sieve of Eratosthenes to generate the primes in
sequence.

The general principle is that we maintain a dictionary of
composite integers. The meaning of each composite integer is
one of its prime divisors.

Rather than atempt to describe the program in general terms,
I'll step through the program for the first few sequential
prime numbers.

First call:

Yield 2 as first prime.
2 is the first prime. 2 is the only even prime.

From this point onward, only the odd integers are
considered.

Second call:

3 is not in dictionary.
Since 3 is not in the dictionary, it is prime.
3*3 = 9.

Dictionary is now {[9,3]}.

Yield 3 as next prime.

Third call:

5 is not in dictionary.
Since 5 is not in dictionary, it is prime.
5 * 5 = 25.

Dictionary is now {[9,3],[25,5]}.

Yield 5 as next prime.

Fourth call:

7 is not in dictionary.
Since 7 is not in dictionary, it is prime.
7 * 7 = 49.

Dictionary is now {[9,3],[25,5],[49,7]}.

Yield 7 as next prime.

Fifth call:

9 is in dictionary.
Since 9 is in dictionary, it is composite.
Recorded prime divisor of 9 is 3.
remove [9,3] from dictionary.
6 = 2 * 3.
9 + 6 = 15, is not in dictionary.

Dictionary is now {[15,3],[25,5],[49,7]}.

11 is not in dictionary.
Since 11 is not in dictionary, it is prime.
11 * 11 = 121.

Dictionary is now {[15,3],[25,5],[49,7],[121,11]}.

Yield 11 as next prime.

6th call:

13 is not in dictionary.
Since 13 is not in dictionary, it is prime.
13 * 13 = 169.

Dictionary is now {[15,3],[25,5],[49,7],[121,11],[169,13]}.

Yield 13 as next prime.

7th call:

15 is in dictionary.
Since 15 is in dictionary, it is composite.
3 is recorded prime divisor of 15.
6 = 2 * 3.
15 + 6 = 21 is not in dictionary.
Remove [15,3] from dictionary.

Dictionary is now {[21,3],[25,5],[49,7],[121,11],[169,13]}.

17 is not in dictionary.
Since 17 is not in dictionary, it is prime.
17 * 17 = 289.

Dictionary is now
{[21,3],[25,5],[49,7],[121,11],[169,13],[289,17]}.

Yield 17 as next prime.

8th call:

19 is not in dictionary.
Since 19 is not in dictionary, it is prime.
19 * 19 = 361.

Dictionary is now
{[21,3],[25,5],[49,7],[121,11],[169,13],[289,17],[361,19]}.

Yield 19 as next prime.

9th call:

21 is in dictionary.
Since 21 is in dictionary, it is composite.
3 is recorded prime divisor of 21.
Remove [21,3] from dictionary.
2 * 3 = 6.
21 + 6 = 27 is not in dictionary.

Dictionary is now
{[25,5],[27,3],[49,7],[121,11],[169,13],[289,17],[361,19]}.

23 is not in dictionary.
Since 23 is not in dictionary, it is prime.
23 * 23 = 529.

Dictionary is now
{[25,5], [27,3], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23]}.

Yield 23 as next prime.

10th call:

25 is in dictionary.
Since 25 is in dictionary, it is composite.
5 is recorded prime divisor of 25.
2 * 5 = 10.
25 + 10 = 35 is not in dictionary.
Remove [25,5] from dictionary.

Dictionary is now
{[27,3],[35,5], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23]}.

27 is in dictionary.
Since 27 is in dictionary, it is composite.
3 is recorded prime divisor of 27.
2 * 3 = 6.
27 + 6 = 33 is not in dictionary.
Remove [27,3] from dictionary.

Dictionary is now
{[33,3],[35,5], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23]}.

29 is not in dictionary.
Since 29 is not in dictionary, it is prime.
29 * 29 = 841.

Dictionary is now
{[33,3],[35,5], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23], [841,29]}.

Yield 29 as next prime.

11th call:

31 is not in dictionary.
Since 31 is not in dictionary, it is prime.
31 * 31 = 961.

Dictionary is now
{[33,3],[35,5], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23], [841,29], [961,31]}.

Yield 31 as next prime.

12th call:

33 is in dictionary.
Since 33 is in dictionary, it is composite.
3 is recorded prime divisor of 33.
3 * 2 = 6.
33 + 6 = 39 is not in dictionary.
Remove [33,3] from dictionary.
Dictionary is now
{[35,5], [39,3], [49,7], [121,11], [169,13], [289,17],
[361,19],
[529,23], [841,29], [961,31]}.

35 is in dictionary.
Since 35 is in dictionary, it is composite.
5 is recorded prime divisor of 35.
2 * 5 = 10.
35 + 10 = 45 is not in dictionary.
Remove [35,5] from dictionary.

Dictionary is now
{[39,3], [45,5], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23], [841,29], [961,31]}.

37 is not in dictionary.
Since 37 is not in dictionary, it is prime.
37 * 37 = 1369.

Dictionary is now
{[39,3], [45,5], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23], [841,29], [961,31], [1369,37}.

Yield 37 as next prime.

13th call:

39 is in dictionary.
Since 39 is in dictionary, it is composite.
3 is least prime divisor of 39.
2 * 3 = 6.
39 + 6 = 45 is in dictionary.
45 + 6 = 51 is not in dictionary.
Remove [39,3] from dictionary.

Dictionary is now
{[45,5], [51,3], [49,7], [121,11], [169,13], [289,17],
[361,19], [529,23], [841,29], [961,31], [1369,37]}

41 is not in dictionary.
Since 41 is not in dictionary, it is prime.
41 * 41 = 1681.