寻找素数的快速算法？

问题描述：

首先 - 我在这个论坛中查了很多，我还没有找到足够快的东西。我尝试做一个函数，它返回指定范围内的素数。例如，我使用Eratosthenes筛来完成此功能（使用C＃）。我也试过阿特金的筛但埃拉托色尼一个运行速度更快（在我的实现）：寻找素数的快速算法？

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); 
    }

它运行约两倍的速度比代码&算法我发现...... 有应该找到素数更快的方法，你可以帮帮我吗？

在你在寻找什么样的素数？只需介于0和max int之间？范围又有多宽？ – Gleno 2010-09-27 21:52:00

让我们来说一下类似亿/ 2 – Ohad 2010-09-27 21:56:13

有10万个素数不到10^9，所以预先计算它们会给你一个200MB的表。实际上它只是储存筛子（10^9位是125MB，而且你不需要存储偶数位，所以你可以将它全部放在64MB以下）。 – Gabe 2010-09-27 22:07:28

答

在四处搜寻有关此主题（对于项目Euler）的算法时，我不记得发现任何更快的东西。如果速度真的是问题，你有没有想过只是存储素数，所以你只需要查看它？

编辑：快速谷歌搜索发现this，确认最快的方法将只是页面结果并根据需要查找它们。

多一个编辑 - 你可以找到更多的信息here，本质上是这个话题的重复。那里的顶级职位表明，atkin的筛比现在更快，只要在飞行中生成。

不，这些不是很快，即使我的代码更快。我真的看到一些说速度非常快的东西（为什么我不相信它......）我会明天检查它，我必须去。不管怎么说，还是要谢谢你。（这不是重复其他话题，有慢的答案） – Ohad 2010-09-27 22:27:31

这是一个真棒文章，+1 – 2010-10-28 13:22:38

有算法非常非常快于这个简单的一个，看到我的回答 – 2010-10-28 20:09:31

答

几个意见。

对于速度，预先计算然后从磁盘加载。它超快。我很久以前就在Java中做过。
不要作为数组存储，存储为奇数的位序列。更有效的内存方式
如果你的速度问题是你想让这个特定的计算运行得很快（你需要证明为什么你不能预先计算并从磁盘加载它），你需要编写一个更好的Atkin筛。它更快。但只是稍微。
您还没有表明这些素数的最终用途。我们可能完全错过了一些东西，因为你没有告诉我们这个应用程序。告诉我们一个应用程序的草图，答案将更好地针对您的情况。
为什么地球上你觉得有更快的东西存在？你没有证明你的预感。这是一个非常困难的问题。（也就是找到更快）

测试的主要是这样一个孔，那我完全同意jlv ...只需存储并查找它。事实上，应该有一个全球缓存的全球免费Web服务，它可以提供答案...或者更好，java应该在查找中存储所有素数到max int;在Docker世界中，应该有一个应用程序的图像，提供围绕素数的一系列服务，包括查找。它只需要测试它就可以了，然后在任何你选择的语言中寻找最高性能的方法。 – Beezer 2016-12-05 23:29:00

答

你可以做的比，使用Sieve of Atkin更好，但它是相当棘手的执行它快速和正确。维基百科伪代码的简单翻译可能不够好。

是啊，我试图做阿特金斯筛...我的数组还包含偶数，但我没有碰它们...它比eroathenes筛慢了1.5倍。（我发现的大部分代码都是从我的eroa中加倍的）。当然 - 我甚至使用素数属性，我们说我知道要优化...但它仍然较慢（我的数组中有未使用的字节......这应该不重要）。 – Ohad 2010-09-28 22:48:17

为什么不向你展示这个代码呢？ – Landei 2010-09-29 13:15:42

描述它的文章的作者之一的非常快速的C实现在http://cr.yp.to/primegen.html – Olathe 2010-10-04 01:23:50

答

到目前为止，我的经验中最快的算法是Erathostenes的筛子，其中轮子因子分解为2,3和5，其余数字中的素数表示为字节数组中的位。在我3岁的笔记本电脑的一个核心上的Java中，需要23秒来计算高达10亿次的质数。

随着轮子因数分解，Atkin的筛子减慢了大约两倍，而使用普通的BitSet时，它快了大约30％。参考this answer。

答

我做了一个算法，可以从范围2-90 000 000我350M笔记本找到素数为0.65秒，用C写的....你必须使用位运算，并拥有“代码”重新计算指数你的数组的索引你想要的具体位。例如，如果你想数2皱褶，具体位将是例如.... 10101000 ......所以如果你从左边看......你指数4,6,8 ......完蛋了

寻找素数的快速算法？

相关推荐