# Self-Optimizing Prime Number Generator

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