fork download
copy 
  1. # prime number generator
  2.  
  3. # Global associative array _primegen stores the state of all active prime
  4. # number generators. It is a two-dimensional array with an identifier (a
  5. # positive integer) in its first dimension and an element of state in its
  6. # second dimension, intended only for internal use by the prime number
  7. # generator; it should not be modified by client code. The possibilities are:
  8. #
  9. #     _primegen[k, "init"] -- initial primes 2 and 3 to "prime" the pump (sorry!)
  10. #     _primegen[k, "pgen"] -- the k-number of the internal prime number generator
  11. #     _primegen[k, "c"]    -- the next candidate prime number
  12. #     _primegen[k, "p"]    -- the current largest sieving prime
  13. #     _primegen[k, p]      -- the stride associated with sieving prime p where
  14. #                             p in (3, 5, 7, 11, ...); notice no stride for 2
  15. #
  16. # Global variable _primegen_counter is the largest currently-unused k; it is
  17. # initially zero.
  18. #
  19. # Function primegen_init() creates a new prime number generator that returns
  20. # primes starting from zero. It returns a state number (the k of  the _primegen
  21. # array). Function primegen(k) returns the next prime number from prime number
  22. # sequence k, and resets the _primegen[k] generator state for the next call to
  23. # primegen(k).
  24.  
  25. function primegen_init(    k) {
  26.     k = _primegen_counter++
  27.     _primegen[k,"init"] = 2
  28.     return k }
  29.  
  30. function primegen(k,    pgen,c,p,q,s,m) {
  31.  
  32.     # initial primes 2 and 3
  33.     if ((k,"init") in _primegen) {
  34.         if (_primegen[k,"init"] == 2) {
  35.             _primegen[k,"init"] = 3
  36.             return 2 }
  37.         else {
  38.             delete _primegen[k,"init"]
  39.             return 3 } }
  40.  
  41.     # set up for remaining primes after 3
  42.     if (! (k,"pgen") in _primegen) {
  43.         pgen = primegen_init()
  44.         _primegen[k,"pgen"] = pgen
  45.         p = primegen(pgen)
  46.         p = primegen(pgen)
  47.         _primegen[k,"c"] = 3
  48.         _primegen[k,"p"] = p
  49.         _primegen[k,p] = p+p }
  50.  
  51.     # main prime generation routine
  52.     pgen = _primegen[k,"pgen"]
  53.     c = _primegen[k,"c"]
  54.     p = _primegen[k,"p"]; q = p * p
  55.     while (1) {
  56.         c += 2
  57.         if ((k,c) in _primegen) {
  58.             s = _primegen[k,c]; m = c + s
  59.             delete _primegen[k,c]
  60.             while ((k,m) in _primegen) m += s
  61.             _primegen[k,m] = s }
  62.         else if (c < q) {
  63.             _primegen[k,"c"] = c
  64.             _primegen[k,"p"] = p
  65.             return c }
  66.         else {
  67.             s = p + p; m = c + s
  68.             while ((k,m) in _primegen) m += s
  69.             _primegen[k,m] = s
  70.             p = primegen(pgen); q = p * p } } }
  71.  
  72. BEGIN { ps = primegen_init()
  73.         for (p = primegen(ps); p < 100; p = primegen(ps)) {
  74.             pcount++; printf "%d ", p }
  75.         printf "%d\n", pcount
  76.         for (x in _primegen) print x, _primegen[x] }
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 25
2p 3
2c 5
0111 6
2pgen 3
0p 11
0c 101
0105 14
23 6
1pgen 2
0115 10
0pgen 1
03 6
115 6
1p 5
1c 11
13 6
https://ideone.com/vmBqOE
language:
AWK (gawk 4.2.1)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!