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.


 
Module CheckPrimes {
      \\ Inventories are lists, Known and Known1 are pointers to Inventories
      Inventory Known=1:=2@,2:=3@,3:=5@
      Inventory Known1=2@, 3@, 5@
      \\ In a lambda all closures are copies
      \\ but Known and Know1 are copies of pointers
      \\ so are closures like by reference
      PrimeNth=lambda  Known, Known1  (n as long) -> {
            if n<1 then Error "Only >=1"
            if exist(known, n) then =eval(known) : exit
            if n>5 then {
                 i=len(known1) 
                 x=eval(known1, i-1)+2
            } else  x=5 : i=2
            { 
                  if i=n then  =known(n) : exit
                  ok=false
                  if frac(x) then 1000
                  if frac(x/2) else 1000
                  if frac(x/3) else 1000
                  x1=sqrt(x) : d=5@
                  Repeat 
                        if frac(x/d ) else exit
                        d += 2: if d>x1 then ok=true : exit
                        if frac(x/d) else exit
                        d += 4: if d<= x1 else ok=true: exit
                   Always
      1000    If ok then i++:Append Known, i:=x  : if not exist(Known1, x) then Append Known1, x
                   x+=2 : Loop }
      }
      \\ IsPrime has same closure, Known1
      IsPrime=lambda  Known1 (x as decimal) -> {
            if exist(Known1, x) then =true : exit
            if Eval(Known1, len(Known1)-1)>x then exit
            if frac(x/2) else exit
            if frac(x/3) else exit
            x1=sqrt(x):d = 5@
            {if frac(x/d ) else exit
                  d += 2: if d>x1 then =true : exit
                  if frac(x/d) else exit
                  d += 4: if d<= x1 else =true: exit
                  loop
             }
      }
      \\ fill Known1, PrimeNth is a closure here
      IsPrime2=lambda  Known1, PrimeNth (x as decimal) -> {
            if exist(Known1, x) then =true : exit
            i=len(Known1)
            if Eval(Known1, i-1)>x then exit
            {
                  z=PrimeNth(i)
                  if z<x then loop else.if z=x then =true :exit
                  i++
            }
      }
      Print "First twenty primes"
      n=PrimeNth(20)
      For i=1 to 20  : Print Known(i),: Next i
      Print
      Print "Primes between 100 and 150:"
      c=0     
      For i=100 to 150
            If IsPrime2(i) Then print i, : c++
      Next i
      Print
      Print "Count:", c
      Print "Primes between 7700 and 8000:"
      c=0
      For i=7700  to 8000
            If IsPrime(i) Then print i, : c++
      Next i
      Print
      Print "Count:", c
      Print "200th Prime:"
      Print PrimeNth(200)
      Print "List from 190th to 199th Prime:"
      For i=190 to 199 : Print Known(i), : Next i
      Print
      Print "Wait"
      Refresh  ' because refresh happen on next Print, which take time
      ' using set fast! we get no respond from GUI/M2000 Console
      ' also Esc, Break and Ctrl+C not work
      ' we have to use Refresh each 500 primes to have one Refresh
      Set fast !
      for i=500 to 10000 step 50: m=PrimeNth(i): Print "."; :Refresh:Next i
      Print
      Print "10000th Prime:", PrimeNth(10000)
      ' reset speed to fast (there are three levels: slow/fast/fast!)
      set fast
      Print
      Rem 1 : Print Known
      Rem  2: Print Known1
}
CheckPrimes
 