寻找素数的快速算法？
首先 - 我在这个论坛上检查了很多，但没有找到足够快的东西。 我尝试创建一个函数，返回指定范围内的素数。 例如，我使用埃拉托斯特尼筛法（在 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);
}
它的运行速度大约是代码和代码的两倍。我发现的算法... 应该有一种更快的方法来找到素数，你能帮我吗？
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);
}
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
当搜索有关该主题的算法（针对欧拉项目）时，我不记得找到任何更快的东西。如果速度确实是个问题，您是否考虑过只存储素数，以便您只需要查找它？
编辑：快速谷歌搜索发现这个，确认最快的方法将只是对结果进行分页并根据需要查找它们。
另一项编辑 - 您可以在此处找到更多信息，本质上是这个主题的重复。那里的热门帖子指出，就动态生成而言，阿特金筛子比时代筛子更快。
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?
EDIT: quick google search found this, confirming that the fastest method would be just to page the results and look them up as needed.
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.
迄今为止，根据我的经验，最快的算法是埃拉托斯特尼筛法，对 2、3 和 5 进行轮分解，其中剩余数字中的素数表示为字节数组中的位。在我用了 3 年的笔记本电脑的一个核心上，用 Java 计算 10 亿素数需要 23 秒。
使用轮因子分解时，阿特金筛法的速度大约慢了两倍，而使用普通的 BitSet 则速度大约快 30%。
另请参阅此答案。
The fastest algorithm in my experience so far is the Sieve of Erathostenes with wheel factorization for 2, 3 and 5, where the primes among the remaining numbers are represented as bits in a byte array. In Java on one core of my 3 year old Laptop it takes 23 seconds to compute the primes up to 1 billion.
With wheel factorization the Sieve of Atkin was about a factor of two slower, while with an ordinary
BitSetit was about 30% faster.See also this answer.
我做了一个算法，可以在 350M 笔记本上在 0.65 秒内找到 2-90 000 000 范围内的素数，用 C 编写......你必须使用按位运算并有“代码”来重新计算数组的索引您想要的混凝土钻头的索引。例如，如果你想要数字 2 的折叠，具体位将是例如 ....10101000 ...所以如果你从左读...你会得到索引 4,6,8 ...就是这样
I did an algorithm that can find prime numbers from range 2-90 000 000 for 0.65 sec on I 350M-notebook, written in C .... you have to use bitwise operations and have "code" for recalculating index of your array to index of concrete bit you want. for example If you want folds of number 2, concrete bits will be for example ....10101000 ... so if you read from left ... you get index 4,6,8 ... thats it
几条评论。
为了提高速度，请预先计算然后从磁盘加载。速度超级快。我很久以前就用 Java 做到了。
不要存储为数组，而是将奇数存储为位序列。内存效率更高
如果您的速度问题是您希望此特定计算快速运行（您需要证明为什么不能预先计算并从磁盘加载它），您需要编写更好的阿特金筛。它更快。但只有一点点。
您尚未表明这些素数的最终用途。我们可能会完全遗漏一些东西，因为您没有告诉我们该应用程序。告诉我们应用程序的草图，答案将更适合您的情况。
你到底为什么认为存在更快的东西？你还没有证实你的预感。这是一个非常难的问题。 （也就是找到更快的东西）
Several comments.
For speed, precompute then load from disk. It's super fast. I did it in Java long ago.
Don't store as an array, store as a bitsequence for odd numbers. Way more efficient on memory
If your speed question is that you want this particular computation to run fast (you need to justify why you can't precompute and load it from disk) you need to code a better Atkin's sieve. It is faster. But only slightly.
You haven't indicated the end use for these primes. We may be missing something completely because you've not told us the application. Tell us a sketch of the application and the answers will be targetted better for your context.
Why on earth do you think something faster exists? You haven't justified your hunch. This is a very hard problem. (that is to find something faster)
您可以比使用阿特金筛做得更好，但快速实现它是相当棘手的和正确。维基百科伪代码的简单翻译可能还不够好。
You can do better than that using the Sieve of Atkin, but it is quite tricky to implement it fast and correctly. A simple translation of the Wikipedia pseudo-code is probably not good enough.