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.


with javascript_semantics
if platform()!=JS then free_console() end if
sequence primes = {2,3,5,7}
atom sieved = 10
 
procedure add_block()
integer N = min((sieved-1)*sieved,400000)
sequence sieve = repeat(1,N)    -- sieve[i] is really i+sieved
    for i=2 to length(primes) do -- (evens filtered on output)
        atom p = primes[i], p2 = p*p
        if p2>sieved+N then exit end if
        if p2<sieved+1 then
            p2 += ceil((sieved+1-p2)/p)*p
        end if
        p2 -= sieved
        if and_bits(p2,1)=0 then p2 += p end if
--      if sieve[p2] then           -- dang!
            for k=p2 to N by p*2 do
                sieve[k] = 0
            end for
--      end if
    end for
    for i=1 to N by 2 do
        if sieve[i] then
            primes &= i+sieved
        end if
    end for
    sieved += N
end procedure
 
function is_prime2(integer n)
    while sieved<n do
        add_block()
    end while
    return binary_search(n,primes)>0
end function
 
atom t0 = time()
while length(primes)<20 do add_block() end while
printf(1,"The first 20 primes are: ")   ?primes[1..20]
while sieved<150 do add_block() end while
sequence s = {}
for k=abs(binary_search(100,primes)) to length(primes) do
    integer p = primes[k]
    if p>150 then exit end if
    s &= p
end for
printf(1,"The primes between 100 and 150 are: ")    ?s
s = {}
for i=7700 to 8000 do
    if is_prime2(i) then s&=i end if
end for
printf(1,"There are %d primes between 7700 and 8000.\n",length(s))
for i=1 to iff(platform()=JS?7:8) do
    integer k = power(10,i)
    while length(primes)<k do
        add_block()
    end while
    printf(1,"The %,dth prime is : %d\n",{k,primes[k]})
end for
?time()-t0
if platform()!=JS then {} = wait_key() end if
