阿特金筛网解释 [英] Sieve of Atkin explanation

问题描述

我目前正在做一个项目，我需要一种计算素数的有效方法.我已经使用了 埃拉托色尼筛，但是，我一直在四处寻找，发现 阿特金筛分法 是一种更有效的方法.我发现很难找到这种方法的解释(我已经能够理解！).它是如何工作的?示例代码(最好用 C 或 Python 编写)会很棒.

I am doing a project at the moment and I need an efficient method for calculating prime numbers. I have used the sieve of Eratosthenes but, I have been searching around and have found that the sieve of Atkin is a more efficient method. I have found it difficult to find an explanation (that I have been able to understand!) of this method. How does it work? Example code (preferably in C or python) would be brilliant.

感谢您的帮助，唯一我仍然不明白的是 x 和 y 变量在伪代码中指的是什么.有人可以帮我解释一下吗?

thanks for your help, the only thing that I still do not understand is what the x and y variables are referring to in the pseudo code. Could someone please shed some light on this for me?

推荐答案

维基页面始终是一个很好的起点，因为它完整地解释了算法并提供了注释伪代码.(注:这里有很多细节，而且由于 wiki 网站已经可靠运行，我不会在这里引用.)

The wiki page is always a good place to start, since it explains the algorithm in full and provides commented pseudocode. (N.B. There's a lot of detail, and since the wiki website is reliably up, I won't quote it here.)

对于您提到的特定语言的参考:

For references in the specific languages you mentioned:

• C 实现(优化)
• Python 实现

希望有所帮助.

这篇关于阿特金筛网解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！