Basic Notation.

- “p-x” – a prime number, where x >= 1
- “P-n” – the set of prime numbers { p-1 .. p-n }
- | P-n | – the cardinality of “P-n”

Definitions.

- d-k = the product of the elements of set D-k ( p-1 * p-2 * .. * p-k )
- D-k = the set of primes { p-1 , p-2 .. p-k )

Initialization.

- p-last : defaults to “p-2″=3
- found = 2
- D-found = P-2 = { 2 , 3 }
- d-found = d-2 = 6
- last-found = 3

Data Structure.

- COPRIMES is a bitmap with d-found bits { bit-1 .. bit-(d-found) }
- PRIMES is a bitmap where each the index represents a number of the form (d-found)j + k where j >= 0 and k is in COPRIMES
- PRIMES[index] = represents (d-found)j + k where { j EQUALS TRUNCATE(index / |COPRIMES|) } and { k = index % | COPRIMES | }
- BOTH ARE INITIALIZED TO 0s before the variables above are initialized.
- If a bit in COPRIMES is set to 1, the bit at that index is COPRIME to d-found. Otherwise it will be set to 0.
- If a bit in PRIMES is set to 1, the bit at that index is PRIME. COMPOSITE numbers are set to 0.

Algorithm.

DEF MAIN

. DO INFINATELY :

. INITIALIZE_COPRIMES(d-found)

. FROM i EQUALS (p-last)^2 TO (d-k)^2 STEP (i = (d-found)j + k) where j >= 0 and k ISA COPRIMES :

. retval = PRIMALITY_TEST( i )

. IF (retval == TRUE) THEN

. SET_PRIME( i )

. last-found = i

. END IF

. UPDATE_STRUCTURE()

. END FROM

END MAIN

DEF UPDATE_STRUCTURE

. SET found TO | D-found |

. COMPUTE d-found

. REORGANIZE PRIMES bitmap

END UPDATE_STRUCTURE

Advertisements