Siekin of Atkin – 解释和Java示例

我在维基百科上读过关于阿特金的Sieve，但维基目前还有限。 我正在寻找高水平的阿特金筛选和Java中的一个例子的解释。

谢谢。

Answer 1

您可能（并且可能）知道这里给出的关于素数，复合数和筛子的一些基本思想，但是它们可能有益于其他读者理解算法的本质。 这个答案的一些危险地接近于属于StackOverflow的数学等价物，但我觉得有必要在算法的作用和它如何做之间建立联系。

维基百科关于这个筛子的文章中的三个模块化的对称和二次对来自Atkin和Bernstein论文中的三对，它们用定理（及其certificate）发表了这个筛子的核心并显示它们共同形成素数筛子。 任何一个人只会产生素数，但不会产生所有素数。 需要所有三个才能产生所有素数。

这是一个实现Wikipedia算法的java程序。 我没有声明实现效率，只是它是维基百科文章算法的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给出定理和certificate的三个是基于他们的工作在算法中使用的三个。 阿特金和伯恩斯坦也没有声称他们的三对是最佳的。 它们显然是方便的。

这里没有以简洁的方式对这种讨论非常有用的时髦数学符号。 出于本答案的目的，我将使用

{一些枚举的集合或定义一个的属性}

代表一组

Nat0

表示包括零的自然数集，即Nat0 = {0,1,2，...}，

纳特

表示不包括零的自然数集合，即Nat = {1,2,3，...}和以下用于定义集合的构造及其元素的符号：

{集合元素的符号：根据符号定义集合的条件}

＃

表示集合基数，即集合中的元素数量

^

表示取幂，即x平方写为x ^ 2

在描述，定理和算法中的车轮因子分解中使用的模运算以两种等效forms出现：

n =（k * m）+ r对于Nat0中的k和R中的r = {r：r表示Nat0且r

n mod m = r其中r = R = {r：r在Nat0中且r

以下是他们论文中定理给出的定义以及关于模数算术forms的一些注释：

1. n总是素数＃{（x，y）：n =（4 * x ^ 2）+（y ^ 2），n在{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为素数。 这里注意formsn mod m = r其中r在R中具有m = 4且R = {r：1}。

2. n总是素数＃{（x，y）：n =（3 * x ^ 2）+（y ^ 2），n在{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为素数。 这里注意formsn mod m = r其中r在集合R中具有m = 6并且R = {r：1}。

3. 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整数，其中x> y> = 1 ，n mod 12 = 11且n没有完美的平方因子，则n为素数。 这里注意formsn mod m = r其中r在集合R中具有m = 12并且R = {r：11}。

本文和维基百科文章假定读者很清楚的车轮因子分解的特性是模运算可用于选择性地仅选择不具有某些素因子的整数。 在表格中

n mod m = r，r = R：{r：Nat0，r

如果只选择R相对于m的元素，那么满足表达式的所有整数n将是素数或相对于m的素数。

m相对素数到n意味着它们没有共同的整数除数> 1.相对素数的例子是：2相对素数为3,4相对素数为9,9相对素数为14.理解这对于理解模数运算中使用的余数（残差）以及它们在各种版本的解释和算法中是等价的。

以下将解释定理，算法和解释如何相关。

对于第一个二次方，n =（4 * x ^ 2）+（y ^ 2）：

该定理使用以下forms：

n =（k * 4）+ r其中r = R1 = {r：1}且k为Nat0

这和写作一样

n mod 4 = r其中R1 = {r：1}

注意，它将n定义为必须是从1开始的Nat0中的每隔一个奇数，即{1,5,9,13，...}。

对于算法，可以对m进行各种选择，并且使用右集R，保留定理所示的属性。 该论文的作者和维基百科的文章假设读者已经知道所有这些并将立即认识到它。 对于论文和维基百科文章中使用的m的其他值，等价物是：

n mod 12 = r其中R1在R1a = {r：1,5,9}

n mod 60 = r其中r在R1b = {r：1,5,9,13,17,21,25,29,33,37,41,45,49,53,57}

由于后面解释的两个原因，集合R1a和R1b中的某些元素可以被移除，并且该定理仍然适用。

对于第二个二次方，n =（3 * x ^ 2）+（y ^ 2）：

该定理使用以下forms：

n =（k * 6）+ r其中r = R2 = {r：1}且k为Nat0

再次这是一样的

n mod 6 = r其中R2 = {r：1}

请注意，这是Nat0中从1开始的每三个奇数，即{1,7,13,19，...}

论文和文章中的等价物是：

n mod 12 = r其中R2在R2a = {r：1,7}

n mod 60 = r其中R2在R2b = {r：1,7,13,19,25,31,37,43,49,55}

同样，由于后面解释的两个原因，集合R2a和R2b中的值可以被移除，并且该定理仍然适用。

对于第三个二次方，（3 * x ^ 2） - （y ^ 2）：

该定理使用以下forms：

n = k * 12 + r其中k为Nat0，r为R3a = {r：11}

同样，这与：

n mod 12 = r其中R3a中的r = {r：11}

请注意，这是从11开始的Nat0中每六个奇数，即{11,23,35,47，...}

论文和文章的等价物是：

n mod 60 = r其中r在R3b = {r：11,23,35,47,59}

同样，由于后面解释的原因，可以去除集合R3b中的值，并且该定理仍然适用。

在各种算法和解释中，对于m = 12和m = 60的值，集合R的元素被移除而不影响定理或算法的有效性。 有两个原因使得集合R中的某些值可以被丢弃。

第一个原因是集合R中r的任何值都不是与它配对的m的相对素数，它只能用于n的值，它是具有一个或多个素数因子m的复合整数，其中没有一个将是素数。 模数运算的这一特征是为什么车轮因子分解用于从进一步的测试中过滤出大量的非素数，为什么它们是素数，通常是更复杂和效率更低的。 在这个筛子中，更复杂的测试是特定不可约二次方的解的数量是否是奇数。 这意味着我们可以立即丢弃该算法的集合R中的所有值，该值不会与该集合R使用的m值相关。

第二个原因是在论文中，车轮因子分解创建了重叠的整数集，包括重叠的素数。 虽然它们很方便，但重叠对于定理并不重要，但在算法中如果可以很容易地避免这种情况则是浪费。 在这种情况下，可以避免这种情况。 此外，如果来自车轮分解的整数集重叠，则一个二次方的奇数个解加上另一个二次方的奇数个解将成为累积偶数个解（奇数加奇数总是一个偶数）。 在许多实现中，包括维基百科实现，这将识别素数不是素数，因为像维基百科这样的实现从所有二次方的累积解决方案中推算出素性并且不从每个二次方分离解决方案。 在这些情况下，轮子因子分解中的整数必须是整数的唯一子集。

如果没有必要，实现不希望在多个二次方中测试相同的数字，而事实并非如此。 假设使用相同的m，在三个正方形中使用的集合R中的r的值仅需要在其中一个中。 如果它不止一个，则n的相同值将不止一次出现，并使用多个二次方进行测试。 对于使用中相同的m值，确保R中的相同元素不会出现在R中超过一个二次方将消除重叠。 在维基百科文章的情况下，通过车轮分解防止的重叠防止了在累积四边形解决方案中可能发生的错误结果，在单个二次方是奇数，但在两个方形中，累积到偶数。

在计算二次方程之前，不同的算法可以避免重叠。 在二次曲线和车轮因子分解的经验测试中，m = 12的车轮分解产生的n值明显少于n将解决二次方程。 使用m = 60的车轮分解可显着增加差异。 如果针对n的特定值的二次解算法是高效的，则通过仅使用来自车轮因子分解的值来测试二次曲面可以有显着的改进。

这是在移除不相对素数的元素之后的轮子因子分解。 对于第一个二次方：

n mod 12 = r其中R1中的r = {1：1,5}（9除数3与12相同）

n mod 60 = r其中R1中的r = {r：1,13,17,29,37,41,49,53}（5,25和45的除数5与60相同; 9,21,33,45和57具有与60）相同的除数3，这是Atkin和Bernstein论文中算法的forms。

对于第二个二次方：

n mod 12 = r其中R2在R2a = {1,7}中（R的任何元素都没有12的除数）

n mod 60 = r其中R2中的r = {r：1,7,13,19,31,37,43,49}（25和55的除数5与60相同）这是算法中的forms阿特金和伯恩斯坦的论文。

对于第三个二次方：

n mod 12 = r其中R3a中的r = {r：11}（R的元素没有12的除数）

n mod 60 = 4其中R3中的r = {r：11,23,47,59}（35除数5与60共同），这是Atkin和Bernstein论文中算法的forms。

请注意，一些相同的元素出现在第一和第二个二次方的集合R1a和R2a中。 集合R1b和R2b也是如此。 当m为12时，公共元素集为{1}; 当m为60时，公共元素集合为{1,13,37,49}。 确保R的元素仅包含在一个二次方中，可以创建以下forms，您现在应该从Wikipedia文章中识别这些forms。

对于第一个二次方：

n mod 12 = r其中R1中的r = {r：1,5}（没有重复删除）（这是维基百科算法中显示的forms）

n mod 60 = r其中R1中的r = {r：1,13,17,29,37,41,49,53}（没有重复删除）（这是维基百科解释中显示的forms）

对于第二个二次方：

n mod 12 = r其中R2中的r = {r：7}（元素1已被删除，因为它已经在R1a中）（这是维基百科算法中显示的forms）

n mod 60 = r其中R2中的r = {r：7,19,31,43}（元素1,13,37和49已被删除，因为它们已经在R1b中）（这是维基百科解释中显示的forms）

对于第三个二次方：

n mod 12 = r其中R3a中的r = {r：11}（无重复）

n mod 60 = r其中R3b中的r = {r：11,23,47,59}（无重复）

剩下的一个问题可能是为什么m的值超过4,6,12和60.这与有多少复合（即非素数）数字想要从更复杂的测试排除使用quadratics与使用的车轮分解的复杂性。

使用的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并且设置R2，其中不包含5时，大量的素数（可能是其中的一半）将被排除。

如果m = 12并且R3 = {r：11}，如在第三个二次方程的定理中那样，所有具有2或3的素因子的复合数被消除，因为11对于12是相对素数而12具有2和3的素因子。同样，当m = 12并且设置R3，其不包含1,5或7时，大量的素数，可能远超过它们的一半，将被排除。

Atkin和Bernstein在他们的论文中非正式地表明的一点是，尽管定理中的车轮因素单独地将质数排除在它们各自的二次方程中，但总的来说，三轮因子分解允许所有素数，并且在车轮因素分解的情况下第一和第二个样方，允许显着重叠。 虽然他们没有删除m = 60的算法中的重叠，但维基百科的文章确实在文章算法中设置m = 12，文章说明中m = 60。

对于在他们的定理中使用的二次型Atkin和Bernstein，弱化与它们一起使用的车轮因子分解将使它们​​将根据定理操作无效。 但是，我们可以通过仅删除更多复合材料但仍保持完全相同的素数的方式来加强它们。 对于m = 4，（4 = 2 * 2）的forms，每个偶数整数都被过滤。 对于m = 12（12 = 2 * 2 * 3）的forms，质数因子为2或3的每个整数都被过滤。 对于m = 60（60 = 2 * 2 * 3 * 5）的forms，质数因子为2,3或5的每个整数都被过滤。 我们可以使用m = 6的潜在用途filter，与m = 12和m = 30具有相同的效果，但是我们必须注意我们创建的等同于m = 60中使用的filter。定理。

这里有一些关于车轮分解的有用统计数据。 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整数的简单方法，从更复杂的测试中获得质数是非常诱人的，并且是使用车轮分解作为素数筛的初步filter的动机。 使用m的值和伴随的集合R也是一种动机，它可以过滤所有具有代表大量复合材料的主要因素的复合材料。

作为绝对最小值，人们可能希望删除质数因子为2的复合（即所有偶数），然后在末尾添加2。 人们至少希望去除质数因子为2或3的复合材料。优选地，人们希望去除质数因子为2,3或5的复合材料。过去，复合材料显示收益递减。 m = 4，R1完成最低限度。 m = 12，R1a，R2a和R3a完成了至少一个人想要的。 m = 60，R1b，R2b和R3b实现非常理想的结果。

在处理m和集合R的值时，还有一些事情需要考虑。请注意，这两个forms对于第一个二次方不等效：

n mod 12 = r其中R1在R1a = {r：1,5}

和

n mod 6 = r其中r = R：{r：1,5}

因为m = 6的forms不等同于

n mod 4 = r其中R1 = {r：1}

注意：

n mod 6 = r其中r = R：{r：1}

相当于

n mod 12 = r其中r = R：{r：1,7}

m = 6的forms可以与第二个二次曲线一起使用。 事实上，它是与定理中的第二个二次曲线一起使用的forms。 如果我们使用它而不是已经考虑的例子，我们可以从集合R中删除第一个二次方的元素1，当它的m = 12时去除重叠。

在调整算法时，必须使用尽职调查来维持定理所需的条件。 当选择m的值和R的集合时，必须确保forms是一个等价的forms，它不会将n引入任何新的值，而不是由定理中的轮分解产生的二次曲线。

对于实现，选择是基于涉及数据结构，算术，处理器能力（尤其是乘法和除法），可用处理器高速缓存，存储器和数据结构大小的复杂性和效率而做出的。 m的值与必须检查的集合R中的余数（残差）的数量之间存在权衡。 其中一些可能是在解释中看到m = 60而在算法中m = 12的原因。 它们绝对是Atkin和Bernstein在论文中使用m = 60forms的forms的原因。

在Atkin和Bernstein的论文中，他们还提供了使用格子找到n的特定值的二次方的解的算法。 这些额外的算法允许Atkin和Bernstein创建筛分算法，同时对样方和车轮因子分解进行过滤。 维基百科文章的算法中没有考虑用于具有车轮因子分解的样方的格点导出解的算法。 在维基百科的文章中，穷举的x，y值技术与样方一起使用，并且在二次方返回n的值之后应用车轮因子分解。 同样，这是一个效率问题，必须由实施者来决定。