7

首先 - 我在这个论坛上查了很多，但我没有找到足够快的东西。我尝试创建一个函数来返回指定范围内的素数。例如，我使用 Eratosthenes 的筛子做了这个函数（在 C# 中）。我也尝试了 Atkin 的筛子，但 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);
    }

它的运行速度比我发现的代码和算法快两倍……应该有一种更快的方法来找到素数，你能帮我吗？

4

5 回答 5

9

在搜索有关此主题的算法时（对于 Euler 项目），我不记得找到更快的方法。如果速度真的很重要，您是否考虑过只存储素数以便只需要查找它？

编辑：快速谷歌搜索发现了这一点，确认最快的方法就是对结果进行分页并根据需要进行查找。

再进行一次编辑 - 您可以在此处找到更多信息，基本上是该主题的副本。那里的顶部帖子指出，就动态生成而言，阿特金的筛子比时代更快。

于 2010-09-27T21:57:22.330 回答
2

到目前为止，在我的经验中最快的算法是对 2、3 和 5 进行轮因式分解的 Erathostenes 筛法，其中剩余数字中的素数表示为字节数组中的位。在我用了 3 年的笔记本电脑的一个内核上使用 Java 计算最多 10 亿个素数需要 23 秒。

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

另请参阅此答案。

于 2010-10-28T12:39:00.563 回答
1

我做了一个算法，可以在我用 C 语言编写的 350M 笔记本上找到 2-90 000 000 范围内的素数 0.65 秒......你必须使用按位运算并有“代码”来重新计算数组的索引你想要的混凝土位的索引。例如，如果您想要数字 2 的折叠，具体位将是例如 ....10101000 ...所以如果您从左侧阅读...您会得到索引 4,6,8 ...就是这样

于 2011-03-22T09:50:21.560 回答
0

几条评论。

  1. 为了速度，预先计算然后从磁​​盘加载。它超级快。我很久以前用Java做过。

  2. 不要存储为数组，存储为奇数的位序列。内存效率更高

  3. 如果您的速度问题是您希望此特定计算快速运行（您需要证明为什么不能预先计算并从磁盘加载它），您需要编写更好的 Atkin 筛子。它更快。但只是轻微的。

  4. 您尚未指明这些素数的最终用途。我们可能完全遗漏了一些东西，因为您没有告诉我们申请。告诉我们应用程序的草图，答案将更适合您的上下文。

  5. 为什么你认为存在更快的东西？你没有证明你的预感是正确的。这是一个非常困难的问题。（就是更快地找到东西）

于 2010-09-28T03:39:23.283 回答
0

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

于 2010-09-28T12:06:54.590 回答