# prime number generator # Global associative array _primegen stores the state of all active prime # number generators. It is a two-dimensional array with an identifier (a # positive integer) in its first dimension and an element of state in its # second dimension, intended only for internal use by the prime number # generator; it should not be modified by client code. The possibilities are: # # _primegen[k, "init"] -- initial primes 2 and 3 to "prime" the pump (sorry!) # _primegen[k, "pgen"] -- the k-number of the internal prime number generator # _primegen[k, "c"] -- the next candidate prime number # _primegen[k, "p"] -- the current largest sieving prime # _primegen[k, p] -- the stride associated with sieving prime p where # p in (3, 5, 7, 11, ...); notice no stride for 2 # # Global variable _primegen_counter is the largest currently-unused k; it is # initially zero. # # Function primegen_init() creates a new prime number generator that returns # primes starting from zero. It returns a state number (the k of the _primegen # array). Function primegen(k) returns the next prime number from prime number # sequence k, and resets the _primegen[k] generator state for the next call to # primegen(k). function primegen_init( k) { k = _primegen_counter++ _primegen[k,"init"] = 2 return k } function primegen(k, pgen,c,p,q,s,m) { # initial primes 2 and 3 if ((k,"init") in _primegen) { if (_primegen[k,"init"] == 2) { _primegen[k,"init"] = 3 return 2 } else { delete _primegen[k,"init"] return 3 } } # set up for remaining primes after 3 if (! (k,"pgen") in _primegen) { pgen = primegen_init() _primegen[k,"pgen"] = pgen p = primegen(pgen) p = primegen(pgen) _primegen[k,"c"] = 3 _primegen[k,"p"] = p _primegen[k,p] = p+p } # main prime generation routine pgen = _primegen[k,"pgen"] c = _primegen[k,"c"] p = _primegen[k,"p"]; q = p * p while (1) { c += 2 if ((k,c) in _primegen) { s = _primegen[k,c]; m = c + s delete _primegen[k,c] while ((k,m) in _primegen) m += s _primegen[k,m] = s } else if (c < q) { _primegen[k,"c"] = c _primegen[k,"p"] = p return c } else { s = p + p; m = c + s while ((k,m) in _primegen) m += s _primegen[k,m] = s p = primegen(pgen); q = p * p } } } BEGIN { ps = primegen_init() for (p = primegen(ps); p < 100; p = primegen(ps)) { pcount++; printf "%d ", p } printf "%d\n", pcount for (x in _primegen) print x, _primegen[x] }