algorithm - 寻找素数的快速算法？

标签 algorithm performance primes sieve-of-eratosthenes

<分区>

首先 - 我在这个论坛上查了很多，但没有找到足够快的东西。我尝试创建一个函数，返回指定范围内的质数。例如，我使用 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);
    }

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

最佳答案

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

编辑:快速谷歌搜索找到this ，确认最快的方法只是对结果进行分页并根据需要查找它们。

再编辑一次 - 您可能会找到更多信息 here ，本质上是该主题的副本。那里的顶级帖子指出，就动态生成而言，阿特金的筛法比 eras 的筛法更快。

关于algorithm - 寻找素数的快速算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3808171/