Lady_Aleena, the Sieve of Eratosthenes is a well-known approach to generating primes. To illustrate, suppose you want to generate the primes between 2 and 20 (as neither 0 and 1 are prime, by definition).
- Write out the list of numbers from 2 to 20 (this johngg does by creating a vector, with the bits for 0 and 1 set to 1):
As numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
As vector: 110000000000000000000
Position: 000000000011111111112
012345678901234567890
- For each number not marked off the list, mark off its multiples (johngg does this by setting that bit of the vector to '1'):
- For 2:
As numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
As vector: 110010101010101010101
Position: 000000000011111111112
012345678901234567890
- For 3:
As numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
As vector: 110010101110101110101
Position: 000000000011111111112
012345678901234567890
Because the square root of 20 is approximately 4.5, we don't have to try the exercise with values beyond 5; thus our list of primes would be:
2 3 5 7 11 13 17 19
As vector: 110010101110101110101
Position: 000000000011111111112
012345678901234567890
The vector bits at 2, 3, 5, 7, 11, 13, 17, and 19 are not set (0), indicating those values are prime.
Hope that helps.
Update: 2015-04-01
Updated formatting of example lines to highlight overstrike of values.