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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s