我一直在尝试学习生成素数的算法，并且在Wikipedia上遇到了Atkin的Sieve。我了解算法的几乎所有部分，除了少数部分。这里是问题：
以下是维基百科的伪代码供参考：
// arbitrary search limit limit ← 1000000 // initialize the sieve for i in [5, limit]: is_prime(i) ← false // put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms for (x, y) in [1, √limit] × [1, √limit]: n ← 4x²+y² if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5): is_prime(n) ← ¬is_prime(n) n ← 3x²+y² if (n ≤ limit) and (n mod 12 = 7): is_prime(n) ← ¬is_prime(n) n ← 3x²-y² if (x > y) and (n ≤ limit) and (n mod 12 = 11): is_prime(n) ← ¬is_prime(n) // eliminate composites by sieving for n in [5, √limit]: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit} print 2, 3 for n in [5, limit]: if is_prime(n): print n
您引用的Wikipedia文章中的Atkin伪代码的Sieve包含了问题的答案或Will Ness提供链接的关于该文章的讨论，尽管您可能无法将信息汇总在一起。简短的答案如下：
这三个方程式来自Atkin的数学证明，即所有质数都会作为三个方程式中一个或多个方程式的解，并且对于变量’x’和’y’的所有有效值都具有适当的取模条件，因此他进一步证明了真质数将是那些对这三个方程具有奇数解的数（从False的初始条件转换为奇数次后，将其保留为True），且每个数的模数条件除外，这些数可被平方除发现素数小于或等于被测数的平方根。
真正的Atkin筛子基于一组60模的条件；此伪代码表示简化，其中使用一组模12条件（5×12 = 60），每个方程的条件范围较小-但是，由于引入了冗余，因此导致进行了20％的额外工作新的条件集。这也是原因，此简化的伪代码需要从5开始而不是正常的7开始其素数扫描，并从5的基素开始以5的基素开始进行基本素数平方的自由消除，这是以下因素造成的： 5否则处理不当。进行这种简化的原因可能是为了减轻代码复杂性（必须检查值）而牺牲一些额外的代码开销，
“提醒”（应拼写为 余数 ）由您引用的伪代码中的“ mod”运算符找到，该伪代码表示 模 运算符，可以使用任何一种计算机语言，通常用计算机语言中的“％”符号表示如C，Java，C＃，F＃等。该运算符产生整数 余数 除以除数（数字的第一个，在“ mod”之前）的整数除以除数（数字的第二个，在“ mod”符号之后）。余数仅为四，而不是全模数60算法中使用的16的原因是由于简化为模数12算法的缘故。您会注意到，在模数为12的条件下，“ 4x”条件通过了25，通常会在模数为60的条件下被消除，因此许多包含25作为因数的复合材料需要通过额外的5平方自由校验来消除。同样，55通过“ 3x +”检查，而35通过“ 3x-”检查，对于完整的模60算法，它们不会通过。
正如在Wikipedia文章“讨论”部分所讨论并在上面暗示的那样，引用的伪代码永远不会比甚至只有基本赔率的Eratosthenes（SoE）实现的筛网要快得多，更不用说由于效率低下而使用相同程度的车轮分解的方法了。 ：变量“ x”和“ y”不需要在很多情况下都位于所筛选范围的平方根的整个范围内（在本文中提到），对60模车轮的正确使用可以恢复模数中的冗余。使用模12简化（如上所述），并且二次方程的解中存在模格子模式，因此无需使用算法自动测试使用（计算缓慢）模运算的条件，该算法会根据算法自动跳过那些不满足那些模条件的解。格子图案（在完整的Atkin和Bernstein论文中仅模糊提及）。
要回答您没有提出的问题，但应该回答： “为什么使用Atkin筛子？” 。
实现Atkin筛网（SoA）而不是Eratosthenes筛网（SoE）的主要原因是SOA更快是“ Internet知识”。这种信念有两个原因，如下所示：
“ Internet知识”没有清楚地理解，这些数字仅适用 于同一算法 的给定范围内的性能比与另一给定范围之间的性能比 ，而不是不同算法之间的比较。因此，如以下优化的SoE示例中所示，对于特定的SoE算法的给定筛分范围，SoA可能会以较大的开销开始，因此，无法证明SoA会比SoE更快。
但是，由于2,3,5级别已“嵌入”到算法中，因此SoA对车轮分解的其他级别没有响应，而SoE确实对其他级别做出了响应：使用2,3,5,7车轮因式分解导致大约相同数量的操作，这意味着每个操作都具有相同的性能。人们甚至可以使用比2,3,5,7级别更高的轮子分解级别，以使SoE的操作数量比SoA少16.7％，以获得成比例的更好性能。实际上，实现这些额外级别的车轮分解所需的优化比实现原始优化的SoA的代码复杂度要简单得多。用于实现这些可比较的页面分段实现的内存占用量大致相同，即页面缓冲区的大小加上基本素数数组。
另外，两者都将受益于以“机器状态查找”风格编写的代码，这将有助于使用内联代码和极限循环展开进行更好的优化，但由于SoE是一种更简单的算法，因此与SoA相比，它更适合这种风格。
因此，对于高达约32位数字范围的筛网范围，最大优化的SoE比SoA快约20％（或在进一步的车轮分解时更高）；但是，SoA具有渐近的计算复杂性优势，因此在某些方面会赶上它。该点大约在log（log n）与log（log（2 ^ 32））之比或5的比值为1.2的范围内，或者是10到19幂的2倍的范围-一个非常大的数字。 如果 一个现代台式计算机上的优化运行SoA的分别采取围绕第二的第三计算在32位数字范围的素数，和 如果 该实现是理想的，因为随着线性时间随范围的增加而增加，要计算此范围内的素数大约需要45年。然而，在这些高范围内的质数分析通常是一小块进行的，因此与SoE相比，使用SoA在理论上非常实用，但对于非常大数量的筛子而言，只是一个很小的因素。
EDIT_ADD： 实际上，与较低的范围相比，页面分段的SoE和SoA都不会继续在线性时间上运行这些较大的范围，因为这两个问题都导致“切换”和“淘汰”操作由于不得不跳过而导致效率降低每次跳转大量页面；这意味着两者都将需要修改的算法来处理此“页面跳转”，并且如果这样做的方式存在任何细微差异，则可能会完全消除SoA的非常微弱的优势。SoA在“跳转表”中的项比SoE多得多，大约是所找到的质数个数与该范围的平方根之比成反比，并且这可能会在处理过程中同时添加O（log n）项，但是对于“跳转表”中具有较高条目数的SoA，其常数因子会增加较大。这个额外的事实几乎可以完全抵消SoA相对于SoE的任何优势，即使是在非常大的范围内。此外，SoA在实现三个单独的二次方程式的条件以及“无素数平方”循环而不是仅有素数剔除循环的情况下，为更多情况所需要的更多单独循环具有不变的开销，因此永远不可能有那么低的完全优化后，每个操作的平均计算时间为SoE。 END_EDIT_ADD
EDIT_ADD2： 我认为关于Atkin筛子的大部分困惑是由于问题中引用的Wikipedia文章中的伪代码不足，因此提出了一个更好的伪代码版本，以解决至少与“ x”和“ y”变量的范围以及模数12与模数60的混淆有关的一些缺陷如下：
limit ← 1000000000 // arbitrary search limit // Initialize the sieve for i in {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: is_prime(i) ← false // Put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms. while n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // odd y's if n mod 60 ∈ {1,13,17,29,37,41,49,53}: is_prime(n) ← ¬is_prime(n) while n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd if n mod 60 ∈ {7,19,31,43}: // x's and even y's is_prime(n) ← ¬is_prime(n) while n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all if n mod 60 ∈ {11,23,47,59}: // even/odd odd/even combos is_prime(n) ← ¬is_prime(n) // Eliminate composites by sieving, only for those occurrences on the wheel for n² ≤ limit where n ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free while c ≤ limit, c ← n² × k where k ∈ {1,7,11,13,17,19,23,29, 31,37,41,43,47,49,53,59,...}: is_prime(c) ← false output 2, 3, 5 for n ≤ limit when n ← 60 × k + x where k ∈ {0..} and x ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61}: if is_prime(n): output n
上面的代码看起来很简单并且是一个很好的算法，除了它仍然不比使用相同的2; 3; 5分解因数的基本Eratosthenes筛更快，因为它浪费了几乎一半的内循环切换操作，而失败了模测试。展示：
接下来是重复的4x²+y²模式，在垂直的15个值“ x”（每个值）和水平的15个奇数值“ y”的范围内，对模60进行限定。两者都从一个开始。请注意，它们是关于垂直轴对称的，但对于整个30个数字范围的“ x”值，225中只有128个或450中有256个是有效的切换操作：
0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 37 0 1 0 0 37 0 0 0 37 0 0 1 0 37 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 41 49 0 29 1 41 29 0 29 41 1 29 0 49 41 0 0 49 13 0 0 13 0 13 0 0 13 49 0 0 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 0 0 49 13 0 0 13 0 13 0 0 13 49 0 0 41 49 0 29 1 41 29 0 29 41 1 29 0 49 41 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 37 0 1 0 0 37 0 0 0 37 0 0 1 0 37 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 1 0 0 49 0 1 49 0 49 1 0 49 0 0 1
接下来是重复的3x²+y²模式，在垂直方向上5个奇数值“ x”和水平方向上15个偶数值“ y”的范围内，对模60进行限定。请注意，它们关于水平轴对称，但是对于30个全范围的“ x”值，75个中的48个或450个中的144个是有效的切换操作，因为450个无效操作中的144个都具有偶数“ x”和奇数“ y”已经被消除：
7 19 0 7 43 0 19 19 0 43 7 0 19 7 0 31 43 0 31 7 0 43 43 0 7 31 0 43 31 0 19 31 0 19 0 0 31 31 0 0 19 0 31 19 0 31 43 0 31 7 0 43 43 0 7 31 0 43 31 0 7 19 0 7 43 0 19 19 0 43 7 0 19 7 0
接下来是重复的3x2-y2模式，在垂直方向上5个奇数值“ x”和水平方向15个偶数值“ y”的范围内，对模60进行限定。请注意，它们是关于水平轴对称的，但是对于整个30个数字范围的“ x”值，只有75个中的48个或450个中的224个是有效的切换操作：
59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 23 11 0 23 47 0 11 11 0 47 23 0 11 23 0 11 59 0 11 0 0 59 59 0 0 11 0 59 11 0 23 11 0 23 47 0 11 11 0 47 23 0 11 23 0 59 47 0 59 23 0 47 47 0 23 59 0 47 59 0
接下来是重复的3x2-y2模式，在5个垂直“ x”偶数值和15个水平“ y”奇数值的范围内限定60模。请注意，它们是关于垂直轴对称的，但是对于整个30个数字范围的“ x”值，只有75个中的48个或450个中的224个是有效的切换操作：
11 0 47 23 0 11 23 0 23 11 0 23 47 0 11 47 0 23 59 0 47 59 0 59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 59 47 0 59 23 0 47 11 0 47 23 0 11 23 0 23 11 0 23 47 0 11 59 0 0 11 0 59 11 0 11 59 0 11 0 0 59
通过检查上表可以确定，对于上述伪代码，x的总重复范围为30个值（包括偶数和奇数），在总共1125个组合操作中只有688个有效操作；由于非生产性跳过操作是最内部循环的一部分，因此有条件地跳过值几乎浪费了一半的处理。有两种可能的方法可以有效地消除“命中”冗余，如下所示：
Atkin and Bernstein论文中概述的方法，该方法使用“ x”和“ y”的组合模中的公认模式，仅通过一次在模式上找到给定模的事实来处理模“命中”，那么在某个模数（等于轮位位置）处会有一个无限的值序列，其中每个模式都由一个易于计算的（可变）偏移量分隔开，该偏移量的形式为“当前位置加A乘以’x’的当前值加B ”和“当前位置加C乘以’y’加上D的当前值”，其中A，B，C和D是简单的常量（简单的含义是较小，易于操作）。Bernstein在许多查找表（LUT）的附加帮助下使用了该方法。
通过“ x”的模电流值与“ y”的模数索引的创建总体模式状态查找表（LUT）的方法（上面四个表中的每个表一个，次要素方自由循环一个表）查找要跳过的A，B，C和D参数，而不是跳到下一个样式，而只是跳到水平序列上的下一个位置。这可能是性能更高的选项，因为它更容易使用展开的循环代码的内联来减少每个操作的极端时钟周期，并且当页面分段时由于每个循环的跳转平均较小，在较大范围内将产生更有效的代码。这可能会使每个循环的时钟周期接近高度优化的Eratosthenes筛网的时钟周期，但由于必须计算可变步长而不是能够对SoE使用固定的质数偏移量，因此不太可能降至那么低。
因此，减少主筛运行时间的三个管理目标如下：
成功的筛选减少了操作数量，与高度轮分解的SoE相比，即使经过“命中优化”的SoA失败了，操作次数也减少了约16.7％，范围约为数十亿。
成功的筛选减少了每次操作的CPU时钟周期，与高度优化的SoE（如primesieve）相比，SoA失败了，因为它的操作由于变量增量而更加复杂，再次可能是20％到60％。阿特金和伯恩斯坦的素数（SoA）约为4.5，而素数（SoE）每次操作约需2.5个时钟周期，每次约为10亿，但通过借鉴一些优化技术，也许可以加快SoA的速度。总理。
成功的筛网具有较低的代码复杂度，因此可以使用“桶筛”和其他页面分割优化等技术将其轻松扩展到更大的范围。为此，Atkin筛网不幸地失败了，因为对于大范围的页面分割，它变得越来越复杂。编写一个即使与伯恩斯坦的primegen（SoA）也无法与primesieve竞争的SoA程序非常复杂，而编写接近与primesieve相同性能的代码则相当容易。
成功的筛网的经验复杂度较低，SoA确实比SoE高出（log（log n）），其中n是要筛分的上限范围，但这种较小的比率可能不足以弥补 END_EDIT_ADD2* ，因为上述两个最高的综合损失率随着该系数的减小而减小。 *
因此， “为什么要使用阿特金筛子” 这个问题的答案是 ？ 是 “如果SoE是通过最大的车轮分解优化实现的，那么根本没有理由使用它，直到被筛选的数字非常大（64位数字范围和更高），然后SoA的优势非常小，也许无法实现。所有这些都取决于相对优化中的微小调整。”
