芜湖不芜
它定义了一个生成器- 一个称为“ sieve”的流转换器，Sieve s =
while( True ):
p := s.head
s := s.tail
yield p -- produce this
s := Filter (nomultsof p) s -- go nextprimes := Sieve (Nums 2)它使用等效于匿名函数的咖喱形式nomultsof p x = (mod x p) /= 0两个Sieve和Filter是数据构造与操作的内部状态和通过值参数传递语义。在这里，我们可以看到，最突出的问题这段代码是不是，重复不在于它使用审判庭从工作序列筛选出数倍，而它可以直接将它们找出来，通过在增量计数p。如果我们要用后者代替前者，那么生成的代码将仍然具有极高的运行时复杂性。不，它最明显的问题是它过早地将其Filter放在工作序列的顶部，只有在输入中看到素数平方之后才真正应该这样做。结果，与实际需要的相比，它创建了s 的二次数。它创建的s 链太长，甚至根本不需要它们中的大多数。FilterFilter过滤器的创建被推迟到适当的时候的更正版本是Sieve ps s =
while( True ):
x := s.head
s := s.tail
yield x -- produce this
p := ps.head
q := p*p
while( (s.head) < q ):
yield (s.head) -- and these
s := s.tail
ps := ps.tail -- go next
s := Filter (nomultsof p) s
primes := Sieve primes (Nums 2)或在Haskell中，primes = sieve primes [2..] sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
where (p:pt) = ps (h,t) = span (< p*p) xsrem此处使用而不是，mod因为在某些口译员中它可以更快，并且无论如何这些数字都是正数。通过以问题大小点的运行时间来衡量算法的局部增长阶次，如，我们得到第一个，而第二个正好在上面（以产生的素数计）。t1,t2n1,n2logBase (n2/n1) (t2/t1)O(n^2)O(n^1.4)n只是为了澄清一下，可以用这种（虚构的）语言定义缺少的部分，就像Nums x = -- numbers from x
while( True ):
yield x
x := x+1Filter pred s = -- filter a stream by a predicate
while( True ):
if pred (s.head) then yield (s.head)
s := s.tail另见。更新：奇怪的是，根据AJT Davie在1992年Haskell的书中，David Turner的1976 SASL手册中的第一个代码实例， primes = sieve [2..]
sieve (p:nos) = p : sieve (remove (multsof p) nos)实际上接受并实现了两 对实现-一对用于此问题的试验部门筛网，另一对用于通过计算直接减去每个素数的倍数（也就是真正的Eratosthenes筛子）的有序去除（两者都是当然不推迟）。在Haskell，removemultsof multsof p n = rem n p==0 remove m xs = filter (not . m) xs
multsof p = [p*p, p*p+p..] remove m xs = diff xs m（如果他只是推迟选择实际的实现方式...）至于推迟的代码，在带有“列表模式” 的伪代码中， primes = [2, ...sieve primes [3..]]
sieve [p, ...ps] [...h, p*p, ...nos] =
[...h, ...sieve ps (remove (multsof p) nos)]