快速算法素数？ [英] Fast algorithm for finding prime numbers?

问题描述

首先 - 我在这个论坛上查了很多，我还没有发现的东西速度不够快。 我尽量让一个函数，返回我的素数在规定范围内。 比如我没有使用埃拉托色尼的筛这一功能（在C＃）。我也尝试阿特金的筛但埃拉托色尼持斧更快（在我的实现）：

First of all - I checked a lot in this forum and I haven't found something fast enough. I try to make a function that returns me the prime numbers in a specified range. For example I did this function (in C#) using the sieve of Eratosthenes. I tried also Atkin's sieve but the Eratosthenes one runs faster (in my implementation):

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

它运行两次快于codeS和放大器有关;算法我发现... 有应该是一个更快的方式找到素数，你能帮助我吗？

It runs about twice faster than codes & algorithms I found... There's should be a faster way to find prime numbers, could you help me?

推荐答案

在关于这一主题的算法，摸索（项目欧拉）我不记得找到任何更快。如果速度真是的关注，你有没有想过只是存储的素数，所以你只需要看看它？

When searching around for algorithms on this topic (for project Euler) I don't remember finding anything faster. If speed is really the concern, have you thought about just storing the primes so you simply need to look it up?

编辑：快速谷歌搜索发现，<一个href="http://www.troubleshooters.com/$c$ccorn/primenumbers/primenumbers.htm#_The_Array_Method">this,确认最快的方法是只是页面的结果，并根据需要找一找。

quick google search found this, confirming that the fastest method would be just to page the results and look them up as needed.

还有一个编辑 - 你可能会发现更多的信息<一个href="http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers">here,基本上这个话题的一个副本。顶帖有规定，阿特金的筛比时代'快就产生上飞。

One more edit - you may find more information here, essentially a duplicate of this topic. Top post there states that atkin's sieve was faster than eras' as far as generating on the fly.

这篇关于快速算法素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！