相关疑难解决方法(0)

计算给定数量的除数的最佳算法(性能方面)是什么？

如果您能提供伪代码或链接到一些示例,那将会很棒.

编辑:所有答案都非常有帮助,谢谢.我正在实施Atkin的Sieve,然后我将使用类似于Jonathan Leffler所说的东西.Justin Bozonier发布的链接提供了我想要的更多信息.

在Haskell中,我在Rosetta Code页面上找到了三个简单的Eratosthenes Sieve实现.

现在我的问题是,应该在哪些情况下使用哪一个？

纠正我的初步推理也会有所帮助:

我假设列表一是Haskeller中最惯用且易于阅读的.但是这是正确的吗？我想知道它是否遇到了与另一个基于列表的筛子相同的问题,然后我学会了实际上没有实现算法:(
编辑:这里显示的是我知道有问题的基于列表的筛子,而不是来自RosettaCode的筛子,我贴在底部)

primes = sieve [2..] where
         sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]

在性能方面,不可变阵列似乎是赢家.随着上限m的2000000,这些时间是约:

• 列表的1.3s
• 数组为0.6s
• 可变阵列的1.8s

所以我选择Array来表现.

当然,Mutable Array也很容易推理,因为我有更迫切的语言背景.我不知道为什么我会选择这个,如果我在Haskell编码,因为它既慢于其他人,也不是非惯用的.

此处复制的代码仅供参考:

列表:

primesTo m = 2 : eratos [3,5..m] where
eratos (p : xs) | p*p>m = p : xs
                | True  = p : eratos (xs `minus` [p*p, p*p+2*p..])

minus a@(x:xs) b@(y:ys) = case compare x …