你的问题已经得到了正确的答案。为了完整起见,另一个选项只是添加我们知道永远不会调用的不需要的子句:
primes = next [2 ..]
where
next (p : xs) =
[p] ++ next [x | x <- xs, mod x p > 0]
next _ = undefined
在不相关的注释上,您写道它“运作良好”。不幸的是,虽然确实产生了正确的结果,但它的速度非常慢。它的复杂性是二次的,在产生的素数n中。换句话说,primes !! n
在 中花费时间二次方n
。根据经验,
> primes !! 1000
7927 -- (0.27 secs, 102987392 bytes)
> primes !! 2000
17393 -- (1.00 secs, 413106616 bytes)
> primes !! 3000
27457 -- (2.23 secs, 952005872 bytes)
> logBase (2/1) (1.00 / 0.27)
1.8889686876112561 -- n^1.9
> logBase (3/2) (2.23 / 1.00)
1.9779792870810489 -- n^2.0
而且是不必要的。
下面的代码只需要大约~ n 1.5的时间,给出或取一个对数因子:
{-# LANGUAGE ViewPatterns #-}
primes_ = 2:next primes_ [3 ..]
where
next (p:ps) (span (< p*p) -> (h,xs)) =
h ++ next ps [x | x <- xs, mod x p > 0]
next _ _ = undefined
根据经验,我们再次得到
> primes !! 3000
27457 -- (0.08 secs, 29980864 bytes)
> primes !! 30000
350381 -- (1.81 secs, 668764336 bytes)
> primes !! 60000
746777 -- (4.74 secs, 1785785848 bytes)
> primes !! 100000
1299721 -- (9.87 secs, 3633306112 bytes)
> logBase (6/3) (4.74 / 1.81)
1.388897361815054 -- n^1.4
> logBase (10/6) (9.87 / 4.74)
1.4358377567888103 -- n^1.45
正如我们在这里所看到的,复杂性优势也表现为绝对值的巨大加速。
那么,这个筛子相当于最优试划分,不像问题中的那个。当然,最初提出时,Haskell 还没有视图模式,事实上,还没有 Haskell 本身。