查找素数的快速算法？

Question

首先 - 我在这个论坛上检查了很多,但我找不到足够快的东西.我尝试创建一个函数,返回指定范围内的素数.例如,我使用Eratosthenes的筛子完成了这个功能(在C#中).我也试过阿特金的筛子但是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);
    }

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

Answer 1

当搜索关于该主题的算法时(对于项目Euler)我不记得发现任何更快的东西.如果速度确实是关注的问题,您是否考虑过存储素数以便只需要查找它？

编辑:快速谷歌搜索发现这一点,确认最快的方法只是分页结果,并根据需要查找它们.

还有一个编辑 - 您可以在此处找到更多信息,基本上是本主题的副本.那里的顶级帖子表明,atkin的筛子比现在更快,只要在飞行中产生.