# Extensible prime generator

**Extensible prime generator**

You are encouraged to solve this task according to the task description, using any language you may know.

The task is to 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, (2^{31} 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).

- See also

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

## Ada

The solution is based on an open-ended counter, named "Current" counting up to the limit from the Compiler, namely 2**63-1.

The solution uses the package Miller_Rabin from the Miller-Rabin primality test. When using the gnat Ada compiler, the largest integer we can deal with is 2**63-1. For anything larger, we could use a big-num package.

<lang Ada>with Ada.Text_IO, Miller_Rabin;

procedure Prime_Gen is

type Num is range 0 .. 2**63-1; -- maximum for the gnat Ada compiler MR_Iterations: constant Positive := 25; -- the probability Pr[Is_Prime(N, MR_Iterations) = Probably_Prime] -- is 1 for prime N and < 4**(-MR_Iterations) for composed N function Next(P: Num) return Num is N: Num := P+1; package MR is new Miller_Rabin(Num); use MR; begin while not (Is_Prime(N, MR_Iterations) = Probably_Prime) loop

N := N + 1;

end loop; return N; end Next; Current: Num; Count: Num := 0;

begin

-- show the first twenty primes Ada.Text_IO.Put("First 20 primes:"); Current := 1; for I in 1 .. 20 loop Current := Next(Current); Ada.Text_IO.Put(Num'Image(Current)); end loop; Ada.Text_IO.New_Line; -- show the primes between 100 and 150 Ada.Text_IO.Put("Primes between 100 and 150:"); Current := 99; loop Current := Next(Current); exit when Current > 150; Ada.Text_IO.Put(Num'Image(Current)); end loop; Ada.Text_IO.New_Line; -- count primes between 7700 and 8000 Ada.Text_IO.Put("Number of primes between 7700 and 8000:"); Current := 7699; loop Current := Next(Current); exit when Current > 8000; Count := Count + 1; end loop; Ada.Text_IO.Put_Line(Num'Image(Count)); Count := 10; Ada.Text_IO.Put_Line("Print the K_i'th prime, for $K=10**i:"); begin loop

Current := 1; for I in 1 .. Count loop Current := Next(Current); end loop; Ada.Text_IO.Put(Num'Image(Count) & "th prime:" & Num'Image(Current)); Count := Count * 10;

end loop; exception when Constraint_Error =>

Ada.Text_IO.Put_Line(" can't compute the" & Num'Image(Count) & "th prime:");

end;

end;</lang>

- Output:

First 20 primes: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Primes between 100 and 150: 101 103 107 109 113 127 131 137 139 149 Number of primes between 7700 and 8000: 30 Print the K_i'th prime, for $K=10**i: 10th prime: 29 100th prime: 541 1000th prime: 7919 10000th prime: 104729

(The program is still running to generate larger oputputs.)

## AutoHotkey

<lang AutoHotkey>SetBatchLines, -1 p := 1 ;p functions as the counter Loop, 10000 { p := NextPrime(p) if (A_Index < 21) a .= p ", " if (p < 151 && p > 99) b .= p ", " if (p < 8001 && p > 7699) c++ } MsgBox, % "First twenty primes: " RTrim(a, ", ") . "`nPrimes between 100 and 150: " RTrim(b, ", ") . "`nNumber of primes between 7,700 and 8,000: " RTrim(c, ", ") . "`nThe 10,000th prime: " p

NextPrime(n) { Loop if (IsPrime(++n)) return n }

IsPrime(n) { if (n < 2) return, 0 else if (n < 4) return, 1 else if (!Mod(n, 2)) return, 0 else if (n < 9) return 1 else if (!Mod(n, 3)) return, 0 else { r := Floor(Sqrt(n)) f := 5 while (f <= r) { if (!Mod(n, f)) return, 0 if (!Mod(n, (f + 2))) return, 0 f += 6 } return, 1 } }</lang>

- Output:

First twenty primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 Primes between 100 and 150: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 Number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729

## C

Extends the list of primes by sieving more chunks of integers. There's no serious optimizations. The code can calculate all 32-bit primes in some seconds, and will overflow beyond that. Although it's not difficult to modify the code to deal with longer numbers, it is not really worth doing because for small primes (such as 32-bits) loading pre-computed prime data is always faster, while a list of primes much beyond that has questionable utility at best (and pre-computed data is still faster). <lang c>#include <stdio.h>

- include <stdlib.h>
- include <string.h>
- include <math.h>

- define CHUNK_BYTES (32 << 8)
- define CHUNK_SIZE (CHUNK_BYTES << 6)

int field[CHUNK_BYTES];

- define GET(x) (field[(x)>>6] & 1<<((x)>>1&31))
- define SET(x) (field[(x)>>6] |= 1<<((x)>>1&31))

typedef unsigned uint; typedef struct {

uint *e; uint cap, len;

} uarray; uarray primes, offset;

void push(uarray *a, uint n) {

if (a->len >= a->cap) { if (!(a->cap *= 2)) a->cap = 16; a->e = realloc(a->e, sizeof(uint) * a->cap); } a->e[a->len++] = n;

}

uint low; void init(void) {

uint p, q;

unsigned char f[1<<16]; memset(f, 0, sizeof(f)); push(&primes, 2); push(&offset, 0); for (p = 3; p < 1<<16; p += 2) { if (f[p]) continue; for (q = p*p; q < 1<<16; q += 2*p) f[q] = 1; push(&primes, p); push(&offset, q); } low = 1<<16;

}

void sieve(void) {

uint i, p, q, hi, ptop; if (!low) init();

memset(field, 0, sizeof(field));

hi = low + CHUNK_SIZE; ptop = sqrt(hi) * 2 + 1;

for (i = 1; (p = primes.e[i]*2) < ptop; i++) { for (q = offset.e[i] - low; q < CHUNK_SIZE; q += p) SET(q); offset.e[i] = q + low; }

for (p = 1; p < CHUNK_SIZE; p += 2) if (!GET(p)) push(&primes, low + p);

low = hi;

}

int main(void) {

uint i, p, c;

while (primes.len < 20) sieve(); printf("First 20:"); for (i = 0; i < 20; i++) printf(" %u", primes.e[i]); putchar('\n');

while (primes.e[primes.len-1] < 150) sieve(); printf("Between 100 and 150:"); for (i = 0; i < primes.len; i++) { if ((p = primes.e[i]) >= 100 && p < 150) printf(" %u", primes.e[i]); } putchar('\n');

while (primes.e[primes.len-1] < 8000) sieve(); for (i = c = 0; i < primes.len; i++) if ((p = primes.e[i]) >= 7700 && p < 8000) c++; printf("%u primes between 7700 and 8000\n", c);

for (c = 10; c <= 100000000; c *= 10) { while (primes.len < c) sieve(); printf("%uth prime: %u\n", c, primes.e[c-1]); }

return 0;

}</lang>

- Output:

First 20: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Between 100 and 150: 101 103 107 109 113 127 131 137 139 149 30 primes between 7700 and 8000 10th prime: 29 100th prime: 541 1000th prime: 7919 10000th prime: 104729 100000th prime: 1299709 1000000th prime: 15485863 10000000th prime: 179424673 100000000th prime: 2038074743

## D

This uses a Prime struct defined in the third entry of the Sieve of Eratosthenes task. Prime keeps and extends a dynamic array instance member of uints. The Prime struct has a opCall that returns the n-th prime number. The opCall calls a grow() private method until the dynamic array of primes is long enough to contain the required answer. The function grow() just grows the dynamic array geometrically and performs a normal sieving. On a 64 bit system this program works up to the maximum prime number that can be represented in the 32 bits of an uint. This program is less efficient than the C entry, so it's better to not use it past some tens of millions of primes, but it's enough for more limited usages. <lang d>void main() {

import std.stdio, std.range, std.algorithm, sieve_of_eratosthenes3;

Prime prime; writeln("First twenty primes:\n", 20.iota.map!prime); writeln("Primes primes between 100 and 150:\n", uint.max.iota.map!prime.until!q{a > 150}.filter!q{a > 99}); writeln("Number of primes between 7,700 and 8,000: ", uint.max.iota.map!prime.until!q{a > 8_000} .filter!q{a > 7_699}.walkLength); writeln("10,000th prime: ", prime(9_999));

}</lang>

- Output:

First twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] Primes primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] Number of primes between 7,700 and 8,000: 30 10,000th prime: 104729

## Go

<lang go>package main

import "fmt"

func newP() func() int {

n := 1 // open-ended counter return func() int { for { n++ // count without limit for f := 2; ; f++ { if f == n { return n } if n%f == 0 { break } } } }

}

func main() {

p := newP() fmt.Print("First twenty: ") for i := 0; i < 20; i++ { fmt.Print(p(), " ") } fmt.Print("\nBetween 100 and 150: ") n := p() for n <= 100 { n = p() } for ; n < 150; n = p() { fmt.Print(n, " ") } for n <= 7700 { n = p() } c := 0 for ; n < 8000; n = p() { c++ } fmt.Println("\nNumber beween 7,700 and 8,000:", c) p = newP() for i := 1; i < 10000; i++ { p() } fmt.Println("10,000th prime:", p())

}</lang>

- Output:

First twenty: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Between 100 and 150: 101 103 107 109 113 127 131 137 139 149 Number beween 7,700 and 8,000: 30 10,000th prime: 104729

## Icon and Unicon

Only works in Unicon (use of the Heap class). Brute force. <lang unicon>import Collections # to get the Heap class for use as a Priority Queue record filter(composite, prime) # next composite involving this prime

procedure main()

every writes((primes()\20)||" " | "\n") every p := primes() do if 100 < p < 150 then writes(p," ") else if p >= 150 then break write() every (n := 0, p := primes()) do if 7700 < p < 8000 then n +:= 1 else if p >= 8000 then break write(n) every (i := 1, p := primes()) do if (i+:=1) >= 10000 then break write(p)

end

procedure primes()

local wheel2357, nc wheel2357 := [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10] suspend sieve(Heap(,getCompositeField), ![2,3,5.7] | (nc := 11) | (nc +:= |!wheel2357))

end

procedure sieve(pQueue, candidate)

local nc if 0 = pQueue.size() then { # 2 is prime pQueue.add(filter(candidate*candidate, candidate)) return candidate } while candidate > (nc := pQueue.get()).composite do { nc.composite +:= nc.prime pQueue.add(nc) } pQueue.add(filter(nc.composite+nc.prime, nc.prime)) if candidate < nc.composite then { # new prime found! pQueue.add(filter(candidate*candidate, candidate)) return candidate }

end

- Provide a function for comparing filters in the priority queue...

procedure getCompositeField(x); return x.composite; end</lang>

Output:

->ePrimes 2 3 5.7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 101 103 107 109 113 127 131 137 139 149 30 104729 ->

## J

Using the p: builtin, http://www.jsoftware.com/help/dictionary/dpco.htm reports "Currently, arguments larger than 2^31 are tested to be prime according to a probabilistic algorithm (Miller-Rabin)".

<lang J> p:i.20 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

(#~ >:&100)i.&.(p:inv) 150

101 103 107 109 113 127 131 137 139 149

#(#~ >:&7700)i.&.(p:inv) 8000

30

p:10000-1

104729</lang>

## Perl 6

Build a lazy infinite list of primes using the Perl 6 builtin is-prime method. ( A lazy list will not bother to calculate the values until they are actually used. ) That is the first line. If you choose to calculate the entire list, it is fairly certain that you will run out of process / system memory before you finish... (patience too probably) but there aren't really any other constraints. The is-prime builtin uses a Miller-Rabin primality test with 100 iterations, so while it is not 100% absolutely guaranteed that every number it flags as prime actually is, the chances that it is wrong are about 4^{-100}. Much less than the chance that a cosmic ray will cause an error in your computers CPU. Everything after the first line is just display code for the various task requirements.

<lang perl6>my @primes := gather for 1 .. * { .take if $_.is-prime }

say "The first twenty primes:\n ", "[{@primes[^20].fmt("%d", ', ')}]"; say "The primes between 100 and 150:\n ", "[{@primes.&between(100, 150).fmt("%d", ', ')}]"; say "The number of primes between 7,700 and 8,000:\n ", +@primes.&between(7700, 8000); say "The 10,000th prime:\n ", @primes[9999];

sub between (@p, $l, $u) {

gather for @p { .take if $l < $_ < $u; last if $_ >= $u }

}</lang>

- Output:

The first twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] The primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] The number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729

## Python

The Croft spiral sieve prime generator from the Prime decomposition task is used which contains the line <lang python>islice(count(7), 0, None, 2)</lang>
The call to `count(7)`

is to a generator of integers that counts from 7 upwards with no upper limit set.

The definition `croft`

is a generator of primes and is used to generate as many primes as are asked for, in order.

<lang python>from __future__ import print_function from prime_decomposition import primes from itertools import islice

def p_range(lower_inclusive, upper_exclusive):

'Primes in the range' for p in primes(): if p >= upper_exclusive: break if p >= lower_inclusive: yield p

if __name__ == '__main__':

print('The first twenty primes:\n ', list(islice(primes(),20))) print('The primes between 100 and 150:\n ', list(p_range(100, 150))) print('Thenumberof primes between 7,700 and 8,000:\n ', len(list(p_range(7700, 8000)))) print('The 10,000th prime:\n ', next(islice(primes(),10000-1, 10000)))</lang>

- Output:

The first twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] The primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] The number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729

Alternately, we can use the much simpler infinite primes generator from Sieve of Eratosthenes#Infinite generator. It doesn't have an upper limit; it has an infinite loop (`while True:`

) in the generator function and will keep on generating as many as needed.

<lang python>from __future__ import print_function from sieve_of_eratosthenes_infinite_generator import sieve from itertools import islice

def p_range(lower_inclusive, upper_exclusive):

'Primes in the range' for p in sieve(): if p >= upper_exclusive: break if p >= lower_inclusive: yield p

if __name__ == '__main__':

print('The first twenty primes:\n ', list(islice(sieve(),20))) print('The primes between 100 and 150:\n ', list(p_range(100, 150))) print('Thenumberof primes between 7,700 and 8,000:\n ', len(list(p_range(7700, 8000)))) print('The 10,000th prime:\n ', next(islice(sieve(),10000-1, 10000)))</lang>

- Output:

The first twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] The primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] The number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729

## Racket

Personal note: unless I need the raw power of an application-specific primes generator/filter,
I pretty well stick with the `math/number-theory`

library. And even when I write an ASPG/F I question
how it performs against the `math/number-theory`

version!

The link referenced in the source: `math/number-theory`

module documentation

<lang racket>#lang racket

- Using the prime functions from

(require math/number-theory)

(displayln "Show the first twenty primes.") (next-primes 1 20)

(displayln "Show the primes between 100 and 150.")

- Note that in each of the in-range filters I "add1" to the stop value, so that (in this case) 150 is
- considered. I'm pretty sure it's not prime... but technology moves so fast nowadays that things
- might have changed!

(for/list ((i (sequence-filter prime? (in-range 100 (add1 150))))) i)

(displayln "Show the number of primes between 7,700 and 8,000.")

- (for/sum (...) 1) counts the values in a sequence

(for/sum ((i (sequence-filter prime? (in-range 7700 (add1 8000))))) 1)

(displayln "Show the 10,000th prime.") (nth-prime (sub1 10000)) ; (nth-prime 0) => 2

- If a languages in-built prime generator is extensible or is guaranteed to generate primes up to a
- system limit, (2^31 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).
- Full details in
- [[1]]
- When reading the manual, note that "Integer" and "Natural" are unlimited (or bounded by whatever
- big number representation there is (and the computational complexity of the work being asked).

(define 2^256 (expt 2 256)) 2^256 (next-prime 2^256)

- (Oh, and this is a 64-bit laptop, I left my 256-bit PC in the office.)</lang>

- Output:

Show the first twenty primes. (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71) Show the primes between 100 and 150. (101 103 107 109 113 127 131 137 139 149) Show the number of primes between 7,700 and 8,000. 30 Show the 10,000th prime. 104729 115792089237316195423570985008687907853269984665640564039457584007913129639936 115792089237316195423570985008687907853269984665640564039457584007913129640233

## REXX

Programming note: Most REXXes (of the 32-bit variety) run with an upper limit of roughly 2 Gbytes (for virtual storage), and that is the limit of this program (in building the stemmed array of prime numbers and prime number indicators, and available virtual storage will be the limiting factor of how many primes can be generated.

The method of extending primes (via the PRIMES subroutine) is of two kinds when invoking the PRIMES subroutine:

- a positive number which will (possibly) generate primes up to that total amount, and
- a negative number which will (possibly) generate primes up to |number|.

Two arrays are available to the caller after invoking the PRIMES subrlutine. @.Nth where this is the Nth prime. Also, one can check if 1331 is a prime: !.1331 has the value of 1 (is prime), 0 (isn't prime).

For faster speed, the PRIMES subroutine's logic could be optimized a bit, as well as extending the initial list of low primes (and extending the fixed divisions to reduce the inner DO K loop (divisions of 3───►19).
<lang rexx>/*REXX program finds primes using an extendible prime number generator.*/
parse arg f .; if f==* then f=20 /*allow specifying # for 1 ──► F.*/*
call primes f; do j=1 for f; $=$ @.j; end
say 'first' f 'primes are:' $
say
call primes -150; do j=100 to 150; if !.j==0 then iterate; $=$ j; end
say 'the primes between 100 to 150 (inclusive) are:' $
say
call primes -8000; do j=7700 to 8000; if !.j==0 then iterate; $=$ j; end
say 'the number of primes between 7700 and 8000 (inclusive) is:' words($)
say
call primes 10000
say 'the 10000th prime is:' @.10000
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────PRIMES subroutine───────────────────*/
primes: procedure expose !. s. @. $ #; parse arg H . 1 m .,,$; H=abs(H)
if symbol('!.0')=='LIT' then /*1st time here? Initialize stuff*/

do; !.=0; @.=0; s.=0 /*!.x=some prime; @.n=Nth prime.*/ _=2 3 5 7 11 13 17 19 23 /*generate a bunch of low primes.*/ do #=1 for words(_); p=word(_,#); @.#=p; !.p=1; end #=#-1; !.0=#; s.#=@.#**2 /*set # to be number of primes.*/ end /* [↑] done with building low Ps*/

neg= m<0 /*Neg? Request is for a P value.*/ if neg then if H<=@.# then return /*Have a high enough P already?*/

else nop /*used to match the above THEN. */ else if H<=# then return /*Have a enough primes already ? */

/*─────────────────────────────────────── [↓] gen more P's within range*/

do j=@.#+2 by 2 /*find primes until have H Primes*/ if j//3 ==0 then iterate /*is J divisible by three? */ if right(j,1)==5 then iterate /*is the right-most digit a "5" ?*/ if j//7 ==0 then iterate /*is J divisible by seven? */ if j//11 ==0 then iterate /*is J divisible by eleven? */ if j//13 ==0 then iterate /*is J divisible by thirteen? */ if j//17 ==0 then iterate /*is J divisible by seventeen? */ if j//19 ==0 then iterate /*is J divisible by nineteen? */ /*[↑] above seven lines saves time*/ do k=!.0 while s.k<=j /*divide by the known odd primes.*/ if j//@.k==0 then iterate j /*Is J divisible by P? Not prime.*/ end /*k*/ /* [↑] divide by odd primes √j.*/ #=#+1 /*bump number of primes found. */ @.#=j; s.#=j*j; !.j=1 /*assign to sparse array; prime².*/ if neg then if H<=@.# then leave /*do we have a high enough prime?*/ else nop /*used to match the above THEN. */ else if H<=# then leave /*do we have enough primes yet? */ end /*j*/ /* [↑] keep generating 'til nuff*/

return /*return to invoker with more Ps.*/</lang>
**output** when using the default inputs:

first 20 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 the primes between 100 to 150 (inclusive) are: 101 103 107 109 113 127 131 137 139 149 the number of primes between 7700 and 8000 (inclusive) is: 30 the 10000th prime is: 104729

## Ruby

The prime library behaves like an enumerator. It has an "each" method, which takes an upper bound as argument. This argument is nil by default, which means no upper bound. <lang ruby>require "prime"

puts Prime.take(20).join(", ") puts Prime.each(150).drop_while{|pr| pr < 100}.join(", ") puts Prime.each(8000).drop_while{|pr| pr < 7700}.count puts Prime.take(10_000).last</lang>

- Output:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 30 104729

## Tcl

<lang tcl>package require Tcl 8.6

- An iterative version of the Sieve of Eratosthenes.
- Effective limit is the size of memory.

coroutine primes apply {{} {

yield while 1 {yield [coroutine primes_[incr p] apply {{} {

yield [info coroutine] set plist {} for {set n 2} true {incr n} { set found 0 foreach p $plist { if {$n%$p==0} { set found 1 break } } if {!$found} { lappend plist $n yield $n } }

}}]}

}}

set p [primes] for {set primes {}} {[llength $primes] < 20} {} {

lappend primes [$p]

} puts 1st20=[join $primes ,] rename $p {}

set p [primes] for {set primes {}} {[set n [$p]] <= 150} {} {

if {$n >= 100 && $n <= 150} {

lappend primes $n

}

} puts 100-150=[join $primes ,] rename $p {}

set p [primes] for {set count 0} {[set n [$p]] <= 8000} {} {

incr count [expr {$n>=7700 && $n<=8000}]

} puts count7700-8000=$count rename $p {}

set p [primes] for {set count 0} {$count < 10000} {incr count} {

set prime [$p]

} puts prime10000=$prime rename $p {}</lang>

- Output:

1st20=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71 100-150=101,103,107,109,113,127,131,137,139,149 count7700-8000=30 prime10000=104729

## zkl

fcn postponed_sieve(){ # postponed sieve, by Will Ness

vm.yield(2); vm.yield(3); # original code David Eppstein, vm.yield(5); vm.yield(7); D:=Dictionary(); # ActiveState Recipe 2002 ps:=Utils.Generator(postponed_sieve); # a separate Primes Supply: p:=ps.pump(2,False); # (3) a Prime to add to dict q:=p*p; # (9) when its sQuare is c:=9; # the next Candidate while(1){ if (not D.holds(c)){ # not a multiple of any prime seen so far: if (c < q) vm.yield(c); # a prime, or

else{ # (c==q): # the next prime's square:

add(D,c + 2*p,2*p); # (9+6,6 : 15,21,27,33,...)

p=ps.next(); # (5) q=p*p; # (25) }

}else{ # 'c' is a composite:

s := D.pop(c); # step of increment add(D,c + s,s); # next multiple, same step

} c += 2; # next odd candidate }

}

fcn add(D,x,s){ # make no multiple keys in Dict

while(D.holds(x)){ x += s } # increment by the given step D[x] = s;

}</lang> <lang zkl>var primes = Utils.Generator(postponed_sieve); primes.walk(20).println(); // first 20 primes

primes.pump(List,fcn(p){ // primes between 100 & 150

if (p<100) Void.Skip else if(p>150) Void.Stop else p

}); primes.reduce(fcn(n,p){ // count of primes between 7700 & 8000

if (p<=7700) n else if(p>8000) Void.Stop else n+1

},0); primes = Utils.Generator(postponed_sieve); // 10,000th prime primes.drop(0d9_999); primes.next().println();

// or to carry on until the 100,000th:

primes.pump(Void,fcn(p){primes._n < 0d100_000 and p or Void.Stop}).println(); </lang>

- Output:

L(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71) L(101,103,107,109,113,127,131,137,139,149) 30 104729 1299709