我在 Wikipedia 上阅读了有关 Atkin 筛子的信息，但目前该 wiki 是有限的。我一直在寻找对阿特金筛子的高级解释和 Java 中的示例。
谢谢。
问问题
14381 次
1 回答
133
您可能（并且可能确实）知道这里给出的关于素数、合数和筛子的一些基本概念，但它们可能有助于其他读者理解算法的本质。其中一些答案危险地接近于 StackOverflow 的数学等价物，但我觉得有必要在算法的作用和它的作用方式之间建立联系。
Wikipedia 文章中关于此筛的三个模算术和二次对源自 Atkin 和 Bernstein 论文中的三个对，该论文发表了带有定理（及其证明）的筛的核心，并表明它们共同构成了一个素数筛。任何一个都只会产生素数，但不会产生所有素数。需要全部三个才能产生所有素数。
这是一个实现维基百科算法的java程序。我对实现效率不做任何声明，只是说它是 Wikipedia 文章算法在 java 中的工作直接实现。
// SieveOfAtkin.java
import java.util.Arrays;
public class SieveOfAtkin {
private static int limit = 1000;
private static boolean[] sieve = new boolean[limit + 1];
private static int limitSqrt = (int)Math.sqrt((double)limit);
public static void main(String[] args) {
// there may be more efficient data structure
// arrangements than this (there are!) but
// this is the algorithm in Wikipedia
// initialize results array
Arrays.fill(sieve, false);
// the sieve works only for integers > 3, so
// set these trivially to their proper values
sieve[0] = false;
sieve[1] = false;
sieve[2] = true;
sieve[3] = true;
// loop through all possible integer values for x and y
// up to the square root of the max prime for the sieve
// we don't need any larger values for x or y since the
// max value for x or y will be the square root of n
// in the quadratics
// the theorem showed that the quadratics will produce all
// primes that also satisfy their wheel factorizations, so
// we can produce the value of n from the quadratic first
// and then filter n through the wheel quadratic
// there may be more efficient ways to do this, but this
// is the design in the Wikipedia article
// loop through all integers for x and y for calculating
// the quadratics
for (int x = 1; x <= limitSqrt; x++) {
for (int y = 1; y <= limitSqrt; y++) {
// first quadratic using m = 12 and r in R1 = {r : 1, 5}
int n = (4 * x * x) + (y * y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
sieve[n] = !sieve[n];
}
// second quadratic using m = 12 and r in R2 = {r : 7}
n = (3 * x * x) + (y * y);
if (n <= limit && (n % 12 == 7)) {
sieve[n] = !sieve[n];
}
// third quadratic using m = 12 and r in R3 = {r : 11}
n = (3 * x * x) - (y * y);
if (x > y && n <= limit && (n % 12 == 11)) {
sieve[n] = !sieve[n];
} // end if
// note that R1 union R2 union R3 is the set R
// R = {r : 1, 5, 7, 11}
// which is all values 0 < r < 12 where r is
// a relative prime of 12
// Thus all primes become candidates
} // end for
} // end for
// remove all perfect squares since the quadratic
// wheel factorization filter removes only some of them
for (int n = 5; n <= limitSqrt; n++) {
if (sieve[n]) {
int x = n * n;
for (int i = x; i <= limit; i += x) {
sieve[i] = false;
} // end for
} // end if
} // end for
// put the results to the System.out device
// in 10x10 blocks
for (int i = 0, j = 0; i <= limit; i++) {
if (sieve[i]) {
System.out.printf("%,8d", i);
if (++j % 10 == 0) {
System.out.println();
} // end if
if (j % 100 == 0) {
System.out.println();
} // end if
} // end if
} // end for
} // end main
} // end class SieveOfAtkin
我有一份阿特金（与伯恩斯坦合着）的原始论文，他在其中描述了构造筛子的定理。该论文可在此处获得：http ://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf 。这是非数学家的密集阅读，并且具有美国数学学会论文的所有典型简洁性。
下面是对算法是如何从阿特金和伯恩斯坦的描述和论文中推导出来的更深入的解释。
Atkin 和 Bernstein（有理由地）假设他们的读者完全理解素数筛、模运算和使用模运算的轮因式分解。不幸的是，维基百科的文章描述和算法假设了类似的事情，尽管程度略低。Atkin 和 Bernstein 没有声称他们的三对轮因式分解和不可约二次方程是唯一可以使用的，并给出了其他可以使用的对的示例，而没有进一步评论如何使用。因此，阿特金和伯恩斯坦给出定理和证明的三个是基于他们工作的算法中使用的三个。阿特金和伯恩斯坦也没有声称他们的三对是最优的。显然，它们是方便的。
以简洁的方式对此类讨论真正有用的时髦数学符号在此处不可用。出于此答案的目的，我将使用
{ 一些定义一个的枚举集或属性 }
表示一个集合
Nat0
表示包含零的自然数集合，即 Nat0 = {0, 1, 2, ...}，
纳特
表示不包括零的自然数集合，即 Nat = {1, 2, 3, ...} 和以下用于定义集合的构造和它的元素的符号：
{集合元素的符号：根据符号定义集合的标准}
#
表示集合基数，即集合中元素的数量
^
表示取幂，即 x 平方写为 x^2
描述、定理和算法中的轮因式分解中使用的模运算以两种等效形式出现：
n = (k * m) + r for k in Nat0 and r in R = {r : r in Nat0 and r < m}
n mod m = r 其中 r in R = {r : r in Nat0 and r < m}
以下是他们论文中定理中给出的定义以及关于模算术形式的一些注释：
n 始终是素数，其中 #{(x, y) : n = (4 * x^2 )+ (y^2), n in {n : (Nat0 * 4) + 1}，其中 x 和 y >= 1并且 n 没有完美的平方因子} 是奇数。也就是说，当且仅当有奇数对 (x, y) 对求解二次 n = (4 * x^2) + (y^2) 其中 x 和 y 整数 >= 1, n mod 4 = 1 且 n 没有完全平方因数，则 n 是素数。请注意，形式 n mod m = r 其中 r 在 R 中具有 m = 4 和 R = {r : 1}。
n 总是素数，其中 #{(x, y) : n = (3 * x^2) + (y^2), n in {n : (Nat0 * 6) + 1}，其中 x 和 y >= 1并且 n 没有完美的平方因子} 是奇数。也就是说，当且仅当有奇数对 (x, y) 对求解二次 n = (3 * x^2) + (y^2) 其中 x 和 y 整数 >= 1, n mod 6 = 1 且 n 没有完全平方因数，则 n 是素数。注意这里的形式 n mod m = r 其中 r 在集合 R 中有 m = 6 和 R = {r : 1}。
n 总是素数，其中 #{(x, y) : n = (3 * x^2) - (y^2), {n : (Nat0 * 12) + 11}, x > y >= 1 并且 n 有没有完美的平方因子}是奇数。也就是说，当且仅当有奇数对 (x, y) 对求解二次 n = (3 * x^2) - (y^2) 其中 x , y 整数 where x > y >= 1 , n mod 12 = 11 且 n 没有完全平方因数，则 n 是素数。注意这里的形式 n mod m = r 其中 r 在集合 R 中有 m = 12 和 R = {r : 11}。
论文和维基百科文章假设读者很清楚的轮式分解的一个属性是，可以使用模算术来选择性地仅选择不具有某些素因数的整数。在表格中
n mod m = r, r in R = {r : Nat0, r < m},
如果只选择 R 中与 m 互质的元素，那么满足表达式的所有整数 n 要么是质数，要么与 m 互质。
m 与 n 互质表示它们没有共同的整数除数 > 1。互质数的示例有：2 与 3 互质，4 与 9 互质，9 与 14 互质。理解这一点对于理解模算术中使用的余数（残差）以及它们在各种版本的解释和算法中的等效性。
下面将解释这些定理、算法和解释是如何相互关联的。
对于第一个二次方，n = (4 * x^2) + (y^2)：
该定理使用以下形式：
n = (k * 4) + r 其中 R1 中的 r = {r : 1} 和 Nat0 中的 k
这和写作一样
n mod 4 = r 其中 R1 中的 r = {r : 1}
请注意，它将 n 定义为必须是 Nat0 中从 1 开始的每隔一个奇数，即 {1, 5, 9, 13, ...}。
对于算法，可以对 m 做出各种选择，并且在正确的集合 R 下，定理所示的属性得以保留。这篇论文和维基百科文章的作者假设读者已经知道所有这些并且会立即认出它。对于论文和维基百科文章中使用的其他 m 值，等价物是：
n mod 12 = r 其中 R1a 中的 r = {r : 1, 5, 9}
n mod 60 = r 其中 R1b 中的 r = {r : 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57}
集合 R1a 和 R1b 中的某些元素可以被删除，原因有两个，后面会解释，这个定理仍然适用。
对于第二个二次方，n = (3 * x^2) + (y^2)：
该定理使用以下形式：
n = (k * 6) + r 其中 R2 中的 r = {r : 1} 和 Nat0 中的 k
这又是一样的
n mod 6 = r 其中 R2 中的 r = {r : 1}
这里注意，这是从 1 开始的 Nat0 中每隔三个奇数，即 {1, 7, 13, 19, ...}
论文和文章中的等价物是：
n mod 12 = r 其中 R2a 中的 r = {r : 1, 7}
n mod 60 = r 其中 R2b 中的 r = {r : 1, 7, 13, 19, 25, 31, 37, 43, 49, 55}
同样，集合 R2a 和 R2b 中的值可能会因为后面解释的两个原因而被删除，并且该定理仍然适用。
对于第三个二次方，(3 * x^2) - (y^2)：
该定理使用以下形式：
n = k * 12 + r 其中 Nat0 中的 k 和 R3a 中的 r = {r : 11}
同样，这与以下内容相同：
n mod 12 = r 其中 R3a 中的 r = {r : 11}
这里注意，这是从 11 开始的 Nat0 中每六个奇数，即 {11, 23, 35, 47, ...}
论文和文章的等价物是：
n mod 60 = r 其中 R3b 中的 r = {r : 11, 23, 35, 47, 59}
同样，出于稍后解释的原因，可以删除集合 R3b 中的值，并且该定理仍然适用。
在各种算法和解释中，对于 m = 12 和 m = 60 的值，集合 R 的元素被删除，而不影响定理或算法的有效性。集合 R 中的某些值可能被丢弃有两个原因。
第一个原因是，集合 R 中的任何 r 值如果与其配对的 m 不互质，则仅用于包含 n 的值，这些值是具有一个或多个 m 的质因数的复合整数，其中没有一个将是素数。模算术的这一特性就是为什么使用轮因式分解从进一步的测试中过滤掉大量的非质数，通常是更复杂和效率更低的测试，以确定它们是否是质数。在这个筛子中，更复杂的测试是特定不可约二次方程的解数是否为奇数。这意味着我们可以立即丢弃该算法的集合 R 中的所有值，这些值与与该集合 R 一起使用的 m 的值不是相对质数。
第二个原因是在论文中，轮因式分解创建了重叠的整数集，包括重叠的素数。虽然它们很方便，并且重叠对于定理并不重要，但在算法中，如果可以轻松避免，那就是浪费了。在这种情况下，可以轻松避免。此外，如果车轮因式分解的整数集重叠，则一个二次方程中的奇数解加上另一个二次方程中的奇数解将变成累积偶数解（奇数加奇数总是偶数）。在许多实现中，包括 Wikipedia 实现，这将识别素数作为非素数，因为像 Wikipedia 这样的实现从所有二次方程的累积解决方案中确定素数并且不' t 从每个二次方中分离解。在这些情况下，来自轮因式分解的整数必须是整数的独占子集。
如果没有必要，实现不希望在多个二次方中测试相同的数字，而事实并非如此。在三个二次方中使用的集合 R 中的 r 值，假设使用相同的 m，只需要在其中一个中。如果它不止一个，那么 n 的相同值将出现不止一次，并使用多个二次方进行测试。对于使用的相同 m 值，确保 R 的相同元素不会出现在 R 中超过一个二次方将消除重叠。在 Wikipedia 文章的情况下，轮因式分解防止的重叠防止了累积二次解可能出现的错误结果，这些解在单个二次解中是奇数，但在两个二次解中累积为偶数。
在计算二次方之前，不同的算法可能会避免重叠。在二次方程和车轮分解的经验测试中，m = 12 的车轮分解产生的 n 值明显少于求解二次方程的值。使用 m = 60 的车轮分解会显着增加差异。如果针对特定 n 值的二次求解算法是高效的，那么通过仅使用来自车轮因式分解的值来测试二次方可能会有显着的改进。
这是去除非质数元素后的轮分解。对于第一个二次方：
n mod 12 = r 其中 R1a 中的 r = {1 : 1, 5} （9 的除数 3 与 12 相同）
n mod 60 = r 其中 R1b 中的 r = { r : 1, 13, 17, 29, 37, 41, 49, 53} （5、25 和 45 具有与 60 相同的除数 5；9、21、33、45 和57 的除数 3 与 60 相同），这是 Atkin 和 Bernstein 论文中算法的形式。
对于第二个二次方：
n mod 12 = r 其中 R2a 中的 r = {1, 7}（R 的任何元素都没有与 12 相同的除数}
n mod 60 = r 其中 R2b 中的 r = {r : 1, 7, 13, 19, 31, 37, 43, 49}（25 和 55 的除数 5 与 60 相同），这是算法中的形式阿特金和伯恩斯坦论文。
对于第三个二次方：
n mod 12 = r 其中 R3a 中的 r = {r : 11} （R 的任何元素都没有与 12 相同的除数}
n mod 60 = 4 其中 R3b 中的 r = {r : 11, 23, 47, 59}（35 的除数为 5，与 60 相同），这是 Atkin 和 Bernstein 论文中算法的形式。
请注意，对于第一个和第二个二次方程，一些相同的元素出现在集合 R1a 和 R2a 中。对于集合 R1b 和 R2b 也是如此。m为12时，公共元素的集合为{1}；当 m 为 60 时，公共元素的集合是 {1, 13, 37, 49}。确保仅包含一个二次方的 R 元素会创建以下形式，您现在应该从 Wikipedia 文章中认出这些形式。
对于第一个二次方：
n mod 12 = r where r in R1a = {r : 1, 5}（不删除重复项）（这是维基百科算法中显示的形式）
n mod 60 = r where r in R1b = {r : 1, 13, 17, 29, 37, 41, 49, 53}（不删除重复项）（这是维基百科解释中显示的形式）
对于第二个二次方：
n mod 12 = r where r in R2a = {r : 7} （删除元素 1，因为它已经在 R1a 中）（这是维基百科算法中显示的形式）
n mod 60 = r where r in R2b = {r : 7, 19, 31, 43}（删除元素 1、13、37 和 49，因为它们已经在 R1b 中）（这是维基百科解释中显示的形式）
对于第三个二次方：
n mod 12 = r 其中 R3a 中的 r = {r: 11}（无重复）
n mod 60 = r 其中 R3b 中的 r = {r: 11, 23, 47, 59}（无重复）
剩下的一个问题可能是为什么 m 的值在 4、6、12 和 60 的范围内。这与一个人想要从更复杂的测试中排除多少复合（即非素数）数有关，使用二次方程与使用的车轮分解的复杂性。
使用的 m 值可以确定哪些组合可以立即消除而无需消除素数。如果 m = 4 且 R1 = {r : 1}，如在第一个二次的定理中，所有素因数为 2 的数都被消除，因为 1 与所有数互质，而 4 的素因数为 2。这很重要需要注意的是，因为 3 不在这个集合 R 中，所以使用 m = 4 和集合 R1 的轮因式分解也将排除大量素数，可能是其中的一半。
如果 m = 6 和 R2 = {r : 1}，如第二个二次的定理，则所有素因数为 2 或 3 的合数都将被消除，因为 1 与所有数互质，而 6 的素因数为 2 和 3 . 同样，当 m = 6 并设置不包含 5 的 R2 时，将排除大量素数，也许其中的一半。
如果 m = 12 且 R3 = {r : 11} 与第三次二次的定理一样，则所有素因数为 2 或 3 的合数都将被消除，因为 11 与 12 互质，而 12 的素因数为 2 和 3。同样，当 m = 12 并设置不包含 1、5 或 7 的 R3 时，将排除大量素数，可能超过一半。
Atkin 和 Bernstein 在他们的论文中非正式地表明的一件事是，尽管定理中的轮因式单独排除了它们各自二次方程中的素数，但总的来说，三轮因式分解允许所有素数，并且在轮因式分解的情况下第一个和第二个二次方程允许显着重叠。尽管他们没有删除算法中 m = 60 的重叠，但维基百科文章确实在他们在文章算法中设置 m = 12 和在文章解释中设置 m = 60 的地方。
对于阿特金和伯恩斯坦在他们的定理中使用的二次方程，削弱与他们一起使用的轮因式分解将使它们根据定理运行无效。但是，我们可以通过仅删除更多复合材料但仍保持完全相同的素数的方式来加强它们。对于 m = 4 的形式，(4 = 2 * 2) 每个偶数整数都会被过滤。对于 m = 12 (12 = 2 * 2 * 3) 的形式，每个素因数为 2 或 3 的整数都会被过滤。对于 m = 60 (60 = 2 * 2 * 3 * 5) 的形式，质因数为 2、3 或 5 的每个整数都会被过滤。我们可以使用 m = 6 的过滤器来获得与 m = 12 相同的效果，m = 30 来获得与 m = 60 相同的效果，但我们必须小心我们创建的内容与在定理。
这里有一些关于车轮分解的有用统计数据。Nat0 中 50% 的整数是偶数，除 2 外，不是素数。Nat0 中 33% 的整数以 3 作为质因数且不是质数。Nat0 中 20% 的整数以 5 作为质因数且不是质数。总的来说，Nat0 中 67% 的整数具有 2 或 3 的质因数并且不是质数。总的来说，Nat0 中大约 75% 的整数具有 2、3 或 5 的质因数并且不是质数。从更复杂的素数测试中消除 Nat0 中整数的 1/2、2/3 或 3/4 的简单方法非常诱人，并且是使用轮因式分解作为素数筛中的初步过滤器的动机。这也是使用 m 值和伴随集合 R 的动机，该集合 R 可以过滤所有具有代表大量复合材料的素因子的复合材料。
作为绝对最小值，人们会想要删除素因数为 2（即所有偶数）的复合数，然后在最后加回 2。一个人至少会喜欢去除素因数为 2 或 3 的复合物。最好是去除素因数为 2、3 或 5 的复合物。除此之外，统计数据显示收益递减。m = 4 和 R1 达到了最低限度。m = 12 与 R1a、R2a 和 R3a 一起完成最少的一项。m = 60，R1b、R2b 和 R3b 实现了非常理想的结果。
在处理 m 和集合 R 的值时，还有一些事情需要考虑。请注意，这两种形式对于第一个二次方不等价：
n mod 12 = r 其中 R1a 中的 r = {r : 1, 5}
和
n mod 6 = r 其中 R 中的 r = {r : 1, 5}
因为 m = 6 的形式不等于
n mod 4 = r 其中 R1 中的 r = {r : 1}
注意：
n mod 6 = r 其中 R 中的 r = {r : 1}
相当于
n mod 12 = r 其中 R 中的 r = {r : 1, 7}
m = 6 的形式可以与第二个二次方一起使用。事实上，它是与定理中的第二个二次方一起使用的形式。如果我们使用它来代替已经考虑过的示例，我们可以在第一个二次方的 m = 12 时从集合 R 中删除元素 1 以消除重叠。
在调整算法时，必须尽职尽责地保持定理所需的条件。在选择 m 的值和 R 的集合时，必须确保该形式是等价的，不会将 n 的任何新值引入二次方，这些新值不是由定理中的轮因式分解产生的。
对于实现，根据涉及数据结构、算术、处理器能力（尤其是乘法和除法）、可用处理器高速缓存、内存和数据结构大小的复杂性和效率做出选择。在 m 的值和必须检查的集合 R 中的余数（残数）之间存在权衡。其中一些可能是在解释中看到 m = 60 而在算法中看到 m = 12 的原因。这无疑是 Atkin 和 Bernstein 在他们的论文中的算法中使用 m = 60 的形式的原因。
在 Atkin 和 Bernstein 的论文中，他们还提供了算法，用于使用格子找到特定 n 值的二次方程的解。这些额外的算法使 Atkin 和 Bernstein 能够创建同时过滤二次和轮分解的筛算法。Wikipedia 文章的算法中没有考虑使用车轮分解的二次方程的格派生解的算法。在 Wikipedia 文章中，详尽的 x、y 值技术与二次方一起使用，并且在二次方返回 n 值之后应用车轮分解。同样，这是一个必须由实施者决定的效率问题。
于 2012-08-22T04:22:07.043 回答