Sieve of Eratosthenes 的 Haskell/Scheme 实现

win_hate

有点明白了

按我对第二段代码的理解，设当前素数为 p，你把后面的数分成前后两段。只用 p 来筛后段，而前段让 p 之前的素数来筛。

但是你分段的时候，是通过计算平方来判断的，这与直接拿 p 来模相比，效率不会有明显改进。而且，用 p 来模可以去掉一些合数，计算平方并不能去掉合数，仅仅是把淘汰的工作留给 p 之前的素数了。基于这些分析，第二段代码性能可能不如第一段。

win_hate

我说的平方优化和你的还不大一样，学着用 Haskell 写了一个(逻辑上跟我前面的 scheme 是一致的)。

1. 
   
2. isprime :: Integer->[Integer]->Bool
   
3. isprime n (x:xs) | x*x > n = True
   
4.                  | n `mod` x == 0 = False
   
5.                  | otherwise = isprime n xs
   
6.                               
   
7. 
   
8. primes = 2: filter (\x->isprime x primes) [3..]
   

复制代码

[ 本帖最后由 win_hate 于 2008-9-24 22:46 编辑 ]

win_hate

恩， list comprehension 的确是很漂亮的表达方式。