Each composite number is the product of at least two prime numbers, and
the prime numbers are {2, 3, 4, 5, 6, ...} with
the composite numbers removed:
let rec
merge = lambda a. lambda b.
{assume a and b infinite and disjoint}
let a1=hd a, b1=hd b
in if a1 < b1 then a1::(merge (tl a) b)
else {a1 > b1} b1::(merge a (tl b)),
mult = lambda a. lambda b. (a * hd b)::(mult a tl b),
remove = lambda a. lambda b.
{ a-b, treat lists as sets. PRE: a & b ascending }
if hd a < hd b then (hd a)::(remove tl a b)
else if hd a > hd b then remove a tl b
else remove tl a tl b,
from = lambda n. n::(from (n+1)),
{ n::(n+1)::(n+2):: ... }
products = lambda l. { PRE: l ascending }
let rec p = (hd l * hd l) :: { & elts coprime }
(merge (mult hd l (merge tl l p))
(products tl l))
in p,
first = lambda n. lambda l.
if n <= 0 then nil else hd l :: first (n-1) tl l
in let rec
composites = products primes,
primes = 2 :: (remove (from 3) composites) { ! }
in first 10 primes
{\fB Composites and Primes. \fP}
If the first prime is 2,
the first composite must be 4=2×2 and hence 3 is the second prime,
the second composite must be 6=2×3 and the third prime is 5,
and so on.