又是求素数

2007-08-08 13:34:38 来自: AlbertLee

List> nubBy (( (>1).) . gcd) [2..100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

试试这个：
List> nubBy (( (>1).) . gcd) [2..]

2007-08-08 15:02:45 AlbertLee

对这个小程序的解释：

nub 是除去一个列表中的重复元素， nubBy 则需要一个判断函数
nubBy :: (a -> a -> Bool) -> [a] -> [a]

(( (>1).) . gcd) 这个判断函数
List> :t (( (>1).) . gcd)
(flip (>) 1 .) . gcd :: Integral a => a -> a -> Bool
判断两个数的最大公约数是否大于1

合起来就是：列表[2..] 中没有最大公约数大于1的数对。与质数的定义等价。

> 删除
2007-08-08 17:33:44 氷の鋭 (神不为者，人为之)

List.nubBy (( (>1).) . gcd) [2..]
普通的都是在列表里 filter。不过 nubBy 的实现很慢吧。
nubBy eq l = nubBy' l []
where
nubBy' [] _ = []
nubBy' (y:ys) xs
| elem_by eq y xs = nubBy' ys xs
| otherwise = y : nubBy' ys (y:xs)
只能说，对于 Haskell 来说不算慢的。

> 删除
2009-07-04 02:32:12 Jnny

到后来会越来越慢的~

见这个小组没什么人气回个老帖拉拉高~

> 删除
2009-07-04 02:33:41 Jnny

到差不多9000的时候就是1秒出1个的了...

> 删除
2009-08-08 14:51:29 Fleurer (白天不懂夜的黑)

大素数就只有费马小定理那类的素数测试靠谱了

> 删除