Task

Write a generator of prime numbers, in order, that will automatically adjust to accommodate the generation of any reasonably high prime.

The routine should demonstrably rely on either:

 Being based on an open-ended counter set to count without upper limit other than system or programming language limits. In this case, explain where this counter is in the code.
 Being based on a limit that is extended automatically. In this case, choose a small limit that ensures the limit will be passed when generating some of the values to be asked for below.
 If other methods of creating an extensible prime generator are used, the algorithm's means of extensibility/lack of limits should be stated.


The routine should be used to:

 Show the first twenty primes.
 Show the primes between 100 and 150.
 Show the number of primes between 7,700 and 8,000.
 Show the 10,000th prime.


Show output on this page.

Note: You may reference code already on this site if it is written to be imported/included, then only the code necessary for import and the performance of this task need be shown. (It is also important to leave a forward link on the referenced tasks entry so that later editors know that the code is used for multiple tasks).

Note 2: If a languages in-built prime generator is extensible or is guaranteed to generate primes up to a system limit, (231 or memory overflow for example), then this may be used as long as an explanation of the limits of the prime generator is also given. (Which may include a link to/excerpt from, language documentation).

Note 3:The task is written so it may be useful in solving the task   Emirp primes   as well as others (depending on its efficiency).





Reference

 Prime Numbers. Website with large count of primes.


import tables
 
type PrimeType = int
 
proc primesHashTable(): iterator(): PrimeType {.closure.} =
  iterator output(): PrimeType {.closure.} =
    # some initial values to avoid race and reduce initializations...
    yield 2.PrimeType; yield 3.PrimeType; yield 5.PrimeType; yield 7.PrimeType
    var h = initTable[PrimeType,PrimeType]()
    var n = 9.PrimeType
    let bps = primesHashTable()
    var bp = bps() # advance past 2
    bp = bps(); var q = bp * bp # to initialize with 3
    while true:
      if n >= q:
        let inc = bp + bp
        h[n + inc] = inc
        bp = bps(); q = bp * bp
      elif h.hasKey(n):
        var inc: PrimeType
        discard h.take(n, inc)
        var nxt = n + inc
        while h.hasKey(nxt): nxt += inc # ensure no duplicates
        h[nxt] = inc
      else: yield n
      n += 2.PrimeType
  output
 
var num = 0
stdout.write "The first 20 primes are:  "
var iter = primesHashTable()
for p in iter():
  if num >= 20: break else: stdout.write(p, " "); num += 1
echo ""
stdout.write "The primes between 100 and 150 are:  "
iter = primesHashTable()
for p in iter():
  if p >= 150: break
  if p >= 100: stdout.write(p, " ")
echo ""
num = 0
iter = primesHashTable()
for p in iter():
  if p > 8000: break
  if p >= 7700: num += 1
echo "The number of primes between 7700 and 8000 is:  ", num
num = 1
iter = primesHashTable()
for p in iter():
  if num >= 10000:
    echo "The 10,000th prime is:  ", p
    break
  num += 1
var sum = 0
iter = primesHashTable()
for p in iter():
  if p >= 2_000_000:
    echo "The sum of the primes to two million is:  ", sum
    break
  sum += p