primes - 阿特金筛子解释

Question

我目前正在做一个项目，我需要一种有效的方法来计算素数。我使用了sieve of Eratosthenes，但是我一直在搜索，发现sieve of Atkin是一种更有效的方法。我发现很难找到对此方法的解释(据我所知!)。它是如何工作的？示例代码(最好是C或python)非常出色。

编辑:感谢您的帮助，我仍然不了解的唯一是x和y变量在伪代码中所指的是什么。有人可以帮我一下吗？

Answer 1

wiki page始终是一个很好的起点，因为它完整地解释了算法并提供了注释的伪代码。 (N.B.有很多详细信息，并且由于Wiki网站确实可靠，因此在此不再赘述。)

对于您提到的特定语言的引用:

C implementation(优化)

Python implementation

希望能有所帮助。