寻找质数的快速算法？

Question

寻找质数的快速算法？

algorithmperformanceprimessieve-of-eratosthenes

7

首先，我在这个论坛中查找了很多东西，但没有找到足够快速的东西。我尝试创建一个函数，在指定的范围内返回素数。例如，我使用埃拉托斯特尼筛法编写了此函数（使用C＃）。我也尝试了Atkin's筛法，但Eratosthenes的实现运行得更快：

public static void SetPrimesSieve(int Range)
    {
        Primes = new List<uint>();
        Primes.Add(2);
        int Half = (Range - 1) >> 1;
        BitArray Nums = new BitArray(Half, false);
        int Sqrt = (int)Math.Sqrt(Range);
        for (int i = 3, j; i <= Sqrt; )
        {
            for (j = ((i * i) >> 1) - 1; j < Half; j += i)
                Nums[j] = true;
            do
                i += 2;
            while (i <= Sqrt && Nums[(i >> 1) - 1]);
        }
        for (int i = 0; i < Half; ++i)
           if (!Nums[i])
                Primes.Add((uint)(i << 1) + 3);
    }

它的运行速度比我发现的代码和算法快了两倍左右......应该有更快的方法来查找质数，你能帮我吗？

- Ohad

1

你要在什么范围内寻找质数？只在0和最大整数之间吗？还有这个范围有多宽？ - Gleno

让我们说像十亿除以二这样的东西。 - Ohad

6

小于10^9的素数有5000万个，因此预先计算它们将得到一个200MB的表格。实际上，只需存储筛子（10^9位是125MB，而您不需要存储偶数位，因此可以全部放在64MB以下）会更小。 - Gabe

顺便说一句，我刚刚在我的电脑上运行了 SetPrimesSieve(1e9)，它每秒计算出一百万个质数。我怀疑有很少的算法能够每秒计算超过一百万个东西！ - Gabe

你可以尝试使用多线程版本的算法：http://www.google.com/search?q=parallel+sieve+of+eratosthenes - Sheldon L. Cooper

你可能会对我的文章感兴趣：http://martin-thoma.com/generating-many-prime-numbers/ - Martin Thoma

5个回答

2

我目前使用过的最快算法是埃拉托色尼筛法，其中包含2、3和5的轮子分解，剩余数字中的质数表示为字节数组中的位。在我的三年旧笔记本电脑的一个核心上，使用Java计算1亿以内的质数需要23秒。

使用轮子分解时，阿特金筛法要慢大约两倍，而使用普通的BitSet则要快约30%。

另请参见this answer。

- starblue

1

我写了一个算法，可以在我的C 350M 笔记本电脑上用0.65秒找到2-90,000,000范围内的质数...你必须使用位运算，并具有将数组的索引重新计算为所需比特索引的“代码”。例如，如果您想要数字2的倍数，则具体位将是... 10101000 ... 因此，如果您从左侧阅读...您将得到索引4、6、8...就是这样

- DarkEye

0

几点建议：

为了速度，预先计算然后从磁盘加载。这样非常快。我很久以前就用Java做过。
不要将其存储为数组，而应将其存储为奇数的位序列。这样在内存上更有效率。
如果你的速度问题是你想让这个特定的计算运行得更快（你需要证明为什么不能预先计算并从磁盘加载），你需要编写一个更好的Atkin筛法。它更快。但只是稍微快一点。
你没有说明这些质数的最终用途。因为你没有告诉我们应用程序，所以我们可能会错过一些东西。告诉我们应用程序的概述，答案将更针对你的上下文。
你为什么认为存在更快的方法？你没有证明你的直觉。这是一个非常困难的问题。（即找到更快的方法）

- John

测试质数非常无聊，我完全同意jlv的观点……只需存储并查找即可。实际上，应该有一个免费的全局Web服务，可以缓存全球答案……或者更好的是，Java应该将所有素数存储到max int中进行查找；在Docker世界中，应该有一个具有范围广泛的质数相关服务的应用程序镜像，包括查找。这仅仅是一件让人厌烦的事情，必须测试它，然后寻找你所选择语言中最有效的方法。 - Beezer

0

使用Atkin筛法可以做得比那更好，但是快速且正确地实现它相当棘手。简单翻译维基百科的伪代码可能不够好。

- Landei

是的，我尝试过使用阿特金斯筛法...我的数组中也包含偶数，但我没有处理它们...它比埃拉托色尼筛法慢了1.5倍（我找到的大多数代码都是从我的埃拉托色尼筛法复制的）。当然，我使用了偶素数的属性，并且我知道如何进行优化...但它仍然很慢（我的数组中有未使用的字节...这不应该有影响）。 - Ohad

为什么不把这段代码也展示出来呢？ - Landei

1

一篇论文的作者提供了一个非常快速的C实现，网址为http://cr.yp.to/primegen.html。 - Olathe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jlv · Accepted Answer

当我在寻找这个主题（针对欧拉计划）的算法时，我记不得有找到任何更快的东西。如果速度真的是问题，你是否考虑过只存储素数，这样你只需要查找它们呢？

编辑：快速的谷歌搜索发现this，证实最快的方法就是分页结果，根据需要查找。

再编辑一下 - 你可能会在这里找到更多信息，本质上是这个主题的重复。那里的顶帖表示，Atkin筛选法比Eras筛选法生成更快。