阿特金筛

我一直在尝试学习生成素数的算法，并且在维基百科上发现了阿特金筛法。除了少数几个部分之外，我几乎理解该算法的所有部分。以下是问题：

1. 下面的三个二次方程是如何形成的？ 4x^2+y^2、3x^2+y^2 和 3x^2-y2
2. 维基百科中的算法讨论了模六十，但我不明白下面的伪代码中如何/在何处使用它。
3. 这些提醒1、5、7和11是如何找到的？

下面是来自维基百科的伪代码供参考：

// 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  

The 维基百科文章中的阿特金筛伪代码 http://en.wikipedia.org/wiki/Sieve_of_atkin#Pseudocode您引用的内容包含您的问题的答案或有关 Will Ness 提供链接的文章的讨论，尽管您可能无法将这些信息放在一起。简短回答如下：

1. 这三个方程来自阿特金的数学证明，即所有 素数将作为这三个中的一个或多个的解出现 具有适当模数条件的方程适用于所有有效 变量'x'和'y'的值，事实上他进一步证明了 真正的素数是那些具有奇数个数的数字 这三个方程的解（当切换奇数时保留为 True 初始条件 False) 与模的次数 每个条件不包括那些可被整除的数字 找到的质数的平方小于或等于平方根 测试数。

2. 真正的阿特金筛基于一组模 60 条件； 这个伪代码代表了一种简化，其中更少 使用一组模 12 的每个方程的条件范围 条件 (5 × 12 = 60) - 然而，这导致有 20% 由于在这个新的系统中引入了冗余，正在做额外的工作 一组条件。这也是简化的原因 伪代码需要从 5 开始其主扫描，而不是 正常 7 并进行底素数平方自由消除 从基数 5 开始，但执行时间会增加 因为 5 的因数没有得到正确处理。原因 因为这种简化可能会牺牲一些额外的代码 开销，以减轻必须检查的代码复杂性 值，尽管这可以通过单个表查找来完成 而由于使用模 12 而导致的额外超过 30% 的工作不能 减少。

3. “提醒”（应拼写为余数）由发现 您引用的伪代码中的“mod”运算符代表modulo经常使用任何一种计算机语言的运算符 在C、Java等计算机语言中用“%”符号表示， C#、F# 等等。该运算符产生整数余对被除数进行整数除法后（第一个数字， 在“mod”之前）除以除数（第二个数字，之后 “mod”符号）。余数只有四的原因 而不是完整模 60 算法中使用的 16 是因为 简化为模 12 算法。你会注意到 在模 12 条件下，“4x”条件通过 25 通常可以通过模 60 条件消除，因此许多包含 25 作为因子的复合材料需要 通过 5 平方免费检查的附加素数消除。同样，55 通过“3x+”检查，35 通过“3x-”检查 不适用于完整的模 60 算法。

正如维基百科文章“Talk”部分中所讨论的以及上面所暗示的，这个引用的伪代码永远不会比基本的仅赔率埃拉托色尼筛 (SoE) 实现快得多，更不用说由于效率低下而使用相同程度的轮分解的实现了：变量“x”和“y”不需要在许多情况下（在文章中提到）在整个范围内筛选范围的平方根，正确使用模 60 轮可以恢复冗余使用模 12 简化（正如我上面提到的），并且二次方程的解中有模格子​​模式，这样使用（计算速度慢的）模运算的条件不需要通过使用自动计算的算法来测试根据格子模式跳过那些不满足模条件的解（仅在完整的阿特金和伯恩斯坦论文中非常模糊地提到）。

回答一个你没有问但应该问的问题：“为什么要使用阿特金筛？”.

实施阿特金筛法（SoA）而不是埃拉托斯特尼筛法（SoE）的主要原因是SOA更快是“互联网知识”。这种信念有两个原因，如下：

1. 假设 SoA 更快，因为渐近计算 它的复杂性比 SoE 低 log(log n) 倍 其中 n 是筛选的素数范围。实际上，去 从 2 的 32 次方（四十亿以上）到 2 到 64 的幂（大约 2 后跟 19 个零），这个因数是六 五等于1.2。这意味着真正的 SoE 应该需要 1.2 倍 只要筛分时仅按线性比例预期即可 64 位数字范围与 32 位数字范围相比，而 SoA 将具有线性关系如果一切都是理想的。你 可以理解，首先，对于这样的情况来说，这是一个非常小的因素 数字范围存在巨大差异，其次，这仅带来好处 如果两个算法相同或接近相同则成立 在一些合理的素数范围内的性能。

   那个“互联网知识”还不清楚的是 这些数字仅适用于比较 给定范围内的性能与另一个给定范围内的性能比较对于相同的算法，而不是作为不同之间的比较 算法。因此，作为 SoA 将会存在的证据是没有用的 比 SoE 更快，因为 SoA 可能会以更大的开销启动 对于特定 SoE 算法的给定筛范围，如 以下是优化的 SoE 示例。

2. 由于计算量的原因，SoA 被认为速度更快 阿特金和伯恩斯坦根据他们的观点进行并发表了比较 维基百科文章中链接的论文。虽然工作准确， 它只适用于他们对 他们比较了 SoE 算法：由于 SoA 算法是基于 模 60 因式分解，代表两个 2,3,5 因式分解 车轮旋转，他们也将 SoE 算法限制为相同的 轮分解。这样做，SoE 做了大约 424,000 测试的十亿范围内的复合数剔除操作， 而经测试，完全优化的 SoA 总共约有 326,000 个 切换和方形自由剔除操作，每个操作都需要大约 与 SoE 中的每个合数剔除操作相同的时间，因为 以相同的风格编写。这意味着 SoA 大约是 比 SoE 快 30%对于这组特定的轮分解 状况，这正是阿特金斯和伯恩斯坦的观点 对比测试表明。

   然而，SoA 不响应进一步级别的轮子 因式分解为 2、3、5 级别“内置”到算法中， 而 SoE 确实对进一步的级别做出了响应：使用 2、3、5、7 轮分解导致大约相同数量的操作 这意味着每个人都有相同的表现。人们甚至可以使用 部分车轮分解水平高于2、3、5、7水平 SoE 的操作数量比 SoA 减少约 16.7%， 以获得更好的性能。所需的优化 实现这些额外级别的轮分解实际上是 比实现原始优化的代码复杂度更简单 索阿。实现这些可比页面的内存占用 分段实现大致相同，即大小 页缓冲区加上基本素数数组。

   此外，两者都将受益于用“机器”编写 状态查找”风格，这将有助于更好地优化使用 内联代码和极端循环展开，但 SoE 更适合 这种风格比 SoA 更简单，因为算法更简单。

因此，对于高达大约 32 位数字范围的筛范围，最大优化的 SoE 比 SoA 快大约 20%（或者通过进一步的轮分解更快）；然而，SoA 具有渐进计算复杂性优势，因此它会在某个时刻迎头赶上。该点大约位于 log (log n) 与 log (log (2^32)) 或 5 的比率为 1.2 的范围内，或者大约为 2 乘以 10 的 19 次方的范围内，这是一个非常大的数字。If在现代台式计算机上运行的优化 SoA 需要大约三分之一秒来计算 32 位数字范围内的素数，并且if该实现是理想的，因为随着范围的增加，时间线性增加，计算这个范围的素数大约需要 45 年。然而，对这些大范围内的素数的分析通常是以小块的形式完成的，对于这种情况，与用于非常大的数筛的 SoE 相比，SoA 的使用在理论上是实用的，但系数非常小。

编辑_添加：事实上，与较低范围相比，页面分段 SoE 和 SoA 都无法在这些巨大范围内继续以线性时间运行，因为两者都会遇到“切换”和“剔除”操作由于必须跳过而损失效率的问题每次跳转的页面数量较多；这意味着两者都需要修改算法来处理这种“页面跳转”，并且如果完成此操作的方式存在任何细微差别，SoA 的微小优势可能会被完全消除。 SoA 在“跳转表”中的项比 SoE 多得多，大约是找到的素数数量与该范围的平方根之间的反比，这可能会增加 O(log n)对于处理中的术语而言，但是对于“跳转表”中具有更多条目的 SoA，恒定因子更大的增加。这个额外的事实几乎会完全抵消 SoA 相对于 SoE 的任何优势，即使对于非常大的范围也是如此。此外，SoA 在实现三个单独的二次方程的条件加上“素数平方自由”循环（而不仅仅是素数剔除循环）的更多情况下需要更多单独循环的恒定开销，因此永远不会有那么低的循环开销。完全优化后 SoE 的每个操作的平均计算时间。END_EDIT_ADD

编辑_添加2：我认为，关于阿特金筛的大部分困惑是由于问题中引用的维基百科文章中的伪代码的缺陷造成的，因此提出了一个更好的伪代码版本，至少解决了与“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 分解轮的基本埃拉托色尼筛更快，因为它浪费了几乎一半的内部循环切换操作，这些操作失败了模测试。展示：

以下是重复 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 个是有效的切换操作，因为偶数“x”和奇数的 450 个无效操作中的所有 144 个都是有效的切换操作'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个有效运算；因此，由于非生产性跳过操作是最内层循环的一部分，它浪费了几乎一半的处理时间，只是有条件地跳过值。有两种可能的方法可以低效地消除“命中”冗余，如下所示：

1. Atkin 和 Bernstein 论文中概述的方法，该方法使用“x”和“y”组合模中的已识别模式来仅处理模“命中”，利用这样的事实：一旦在模式上找到给定模，那么在某个模数（等于轮位位置）处有一个无限序列的值，其中每个模式由一个易于计算的（变量）偏移量分隔，其形式为“当前位置加 A 乘以 'x' 的当前值加 B ”和“当前位置加上 C 乘以'y'的当前值加上 D”，其中 A、B、C 和 D 是简单常量（简单意味着小，容易操纵）。 Bernstein 在许多查找表 (LUT) 的额外帮助下使用了该方法。

2. 创建总体模式状态查找表 (LUT)（上述四个表中的每一个表加上一个小素数平方自由循环）的方法，由“x”的模当前值与“y”的模相结合进行索引找到要跳过的 A、B、C 和 D 参数，不是跳到下一个模式，而是跳到水平序列上的下一个位置。这可能是性能更高的选项，因为它更容易允许使用展开循环代码的内联来减少每次操作的极端时钟周期，并且在页面分段时会为大范围生成更高效的代码，因为每个循环的跳转平均较小。这可能会使每个循环的时钟周期接近高度优化的埃拉托色尼筛，如 primesieve 中那样 http://primesieve.org/，但由于必须计算可变步长而不是能够使用 SoE 的固定素数偏移量，因此不太可能达到那么低。

因此，减少主筛的运行时间有以下三个控制目标：

1. 成功的筛选会减少操作次数，与高度轮分解的 SoE 相比，即使是“命中优化”的 SoA 也会失败约 16.7%，范围约为数十亿。

2. 成功的 sieve 会减少每次操作的 CPU 时钟周期，而与高度优化的 SoE（例如 primesieve）相比，SoA 会失败，因为它的操作由于可变增量而变得更加复杂，同样可能增加 20% 到 60%。 Atkin 和 Bernstein 的 primegen (SoA) 大约需要 4.5 个时钟周期，而 primesieve (SoE) 每次操作大约需要 2.5 个时钟周期，每次操作的范围为 10 亿，但或许可以通过借用一些优化技术来加快 SoA 的速度。素筛。

3. 成功的筛选具有相当低的代码复杂性，因此可以使用“桶筛选”和其他页面分段优化等技术更轻松地将其扩展到更大的范围。为此，阿特金筛法惨败，因为它对于大数字范围的页面分段变得更加复杂。编写一个甚至可以与 Bernstein 的 primegen (SoA) 竞争的 SoA 程序是极其复杂的，更不用说与 primesieve 竞争了，而编写与 primesieve 性能接近的代码却相当容易。

4. 成功的筛选具有较低的经验复杂度，SoA 确实比 SoE 高出 (log (log n) 一个因子，其中 n 是要筛选的上限范围，但这个额外的小比率可能不足以弥补对于上述前两个组合损耗率，因为该因子随着范围的增加而变小。END_EDIT_ADD2

所以问题的答案“为什么要使用阿特金筛？” is “如果 SoE 是通过最大轮分解优化来实现的，那么根本没有理由使用它，直到筛选的数字非常大（64 位数字范围及更高），然后 SoA 的优势非常小，甚至可能根本无法实现取决于相对优化中非常小的调整。”.

作为另一个类似的阿特金筛问题的答案，我发布了一个根据上述优化的 SoE 的页面分段 C# 版本：https://stackoverflow.com/a/20559687/549617 https://stackoverflow.com/a/20559687/549617.