Atkin筛网-说明和Java示例

Question

我已经在Wikipedia上阅读了有关Atkin的Sieve的信息，但是目前Wiki受到限制。我一直在寻找有关Atkin的Sieve的高级解释，以及Java的示例。

谢谢。

Answer 1

您可能（并且可能确实）知道这里给出的有关质数，合成数和筛的一些基本思想，但是它们可能会使其他读者受益于理解算法的本质。这个答案有些危险地接近于等同于StackOverflow的数学范围，但是我觉得有必要在算法的作用和方法的作用之间建立联系。

此筛子上Wikipedia文章中的三个模块化算术和二次对是从Atkin和Bernstein论文中的三对算术对中得出的，阿特金和伯恩斯坦论文用定理（及其证明）发布了该筛子的核心，并表明它们共同构成了素数筛子。任何一个人仅会产生质数，而不会产生所有质数。这三者都得出所有素数。

这是一个实现Wikipedia算法的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）（理所当然地）假设他们的读者彻底理解素数筛，模算和使用模算的轮分解。不幸的是，Wikipedia的文章描述和算法采用了类似的方法，尽管程度稍差一些。阿特金（Atkin）和伯恩斯坦（Bernstein）并没有宣称他们的三对轮分解和不可约二次方是唯一可以使用的，并给出了可以使用的其他对的传递示例，而没有进一步说明。因此，Atkin和Bernstein给出定理和证明的三个是基于他们的工作的算法中使用的三个。阿特金（Atkin）和伯恩斯坦（Bernstein）也没有宣称他们的三对是最佳对。显然，它们是方便的。

简明的方式对于此类讨论非常有用的时髦数学符号在这里不可用。为了这个答案的目的，我将使用

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

代表一组

天然0

表示一组自然数，包括零，即Nat0 = {0，1，2，......，

纳特

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

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

＃

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

^

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

在描述，定理和算法中，车轮分解中使用的模块化算法以两种等效形式出现：

n =（k * m）+ r对于在Nat0中的k和R在r中的值= {r：r在Nat0中并且r <m}

n mod m = r其中R中的r = {r：Nat0中的r且r <m}

这是他们的定理中给出的定义，以及有关模数算术形式的一些注释：

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为素数。在此注意，形式n 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为素数。在此请注意，形式为n 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为素数。在此请注意，形式为n mod m = r，其中r在集合R中的m = 12且R = {r：11}。

本文和Wikipedia文章假定读者非常了解轮分解的一个特性是，模块化算术可用于选择性地选择仅不具有某些素数因子的整数。形式

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来保留定理所示的属性。该论文和Wikipedia文章的作者假定读者已经知道所有这些内容，并将立即意识到这一点。对于本文和Wikipedia文章中使用的m的其他值，等效项是：

n mod 12 = r，其中R1a中的r = {r：1，5，9}

n mod 60 = r，其中R1b中的r = {r：1，5，9，13，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}

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

本文和文章中的等效项是：

n mod 12 = r，其中R2a中的r = {r：1，7}

n mod 60 = r，其中R2b中的r = {r：1，7，13，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}

请注意，这是Nat0中从11开始的所有第六个奇数，即{11，23，35，47，…}

本文和文章的等效项是：

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

同样，由于稍后说明的原因，可以删除集合R3b中的值，并且该定理仍然适用。

在各种算法和解释中，对于m = 12和m = 60的值，在不影响定理或算法有效性的情况下，删除了集合R的元素。集合R中的某些值会被丢弃的原因有两个。

第一个原因是，集合R中与配对的m相对质数不是r的任何r值将仅包含n的值，这些n是具有一个或多个质因数m的复合整数，没有一个将是质数。模块化算术的这一特征就是为什么要使用车轮分解来从进一步的测试中滤除大量非素数（通常是更复杂，效率较低的数），以确定它们是否为素数。在这个筛子中，更复杂的测试是特定不可约二次方的解数是否为奇数。这意味着我们可以立即丢弃此算法中集合R中所有与该集合R所使用的m值不是相对质数的值。

第二个原因是，在本文中，车轮分解产生了重叠的整数集，包括重叠的素数。尽管它们很方便，并且对于定理而言，重叠并不重要，但是在算法中，如果可以轻松地避免它是浪费的。在这种情况下，可以避免这种情况。同样，如果车轮分解的整数集重叠，则一个二次方中的奇数个解加上另一个二次方中的奇数个解将变成一个累积的偶数解（一个奇数加一个奇数总是偶数）。在许多实施中，包括Wikipedia实施，这将标识质数为非质数，因为诸如Wikipedia这样的实施从所有二次方的累积解决方案中确定了素数，而不会
t从每个二次方程中分离解决方案。在这些情况下，必须将车轮分解中的整数作为整数的唯一子集。

如果不需要，则实现不希望在多个二次方中测试相同的数字，也没有必要。假设正在使用相同的m，则在三个二次方中使用的集合R中的r值只需在其中一个中。如果大于1，则相同的n值将显示一次以上，并用一个以上的二次方进行测试。对于使用中相同的m值，确保R的相同元素不会在R中出现一个以上的二次方将消除重叠。在Wikipedia文章的情况下，通过车轮因数分解防止的重叠避免了在一个二次方为奇数但在两个二次方中累积为偶数的累积二次解所产生的错误结果。

在计算二次项之前，可以使用其他算法避免重叠。在二次方和车轮分解的经验测试中，m = 12的车轮分解产生的n值明显小于求解二次方的分解。使用m =
60的车轮分解可显着增加差异。如果针对n的特定值的二次解算法非常高效，那么仅使用来自车轮分解的值对二次进行测试，则可能会有重大改进。

以下是除去不太主要的元素之后的车轮分解。对于第一个二次方：

n mod 12 = r，其中R1a中的r = {1：1，5}（9具有与12相同的除数3）

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具有与60相同的除数3），这是Atkin和Bernstein论文算法中的形式。

对于第二个二次项：

n mod 12 = r，其中R2a中的r = {1，7}（R中的任何元素都不具有与12相同的除数）

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

对于第三二次方：

n mod 12 = r，其中R3a中的r = {r：11}（R中的任何元素都不具有与12相同的除数）

n mod 60 = 4，其中R3b中的r =
{r：11，23，47，59}（35具有与60相同的除数5），这是Atkin和Bernstein论文算法中的形式。

注意，对于第一和第二二次方程，在集合R1a和R2a中显示了一些相同的元素。R1b和R2b集也是如此。当m为12时，公共元素集为{1}；当m为60时，公共元素集为{1、13、37、49}。确保R的元素仅包含一个二次方，将创建以下形式，您现在应该从Wikipedia文章中识别出来。

对于第一个二次方：

n mod 12 = r，其中R1a中的r = {r：1，5}（不删除重复项）（这是Wikipedia算法中显示的形式）

n mod 60 = r，其中R1b中的r = {r：1，13，17，29，37，41，49，53}（未删除重复项）（这是维基百科说明中显示的形式）

对于第二个二次项：

n mod 12 = r其中R2a中的r = {r：7}（元素1已删除，因为它已经在R1a中）（这是Wikipedia算法中显示的形式）

n mod 60 = r，其中R2b中的r =
{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值可以确定哪些复合材料可以立即消除而不消除质数。如果m = 4且R1 =
{r：1}，如第一个二次方程的定理所示，所有质数为2的数都将被消除，因为1对所有数都是质数，而4的质数为2。这很重要注意，因为在集合R中不存在3，所以使用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，而12的质数为2和3。同样，当m =
12并设置R3（其中不包含1、5或7）时，大量素数（可能远远超过其中的一半）将被排除。

Atkin和Bernstein在他们的论文中非正式地显示的一件事是，尽管定理中的轮因子分别从它们的二次方程中排除了质数，但是总的来说，三个轮因式分解允许所有素数，并且对于第一和第二二次方允许显着的重叠。尽管他们没有消除m
= 60的算法中的重叠部分，但Wikipedia文章确实在文章算法中将m = 12设置为文章说明，将m = 60设置为。

对于在定理中使用的二次方程式Atkin和Bernstein，削弱与它们伴随的车轮因式分解将使它们​​将根据定理进行运算无效。但是，我们可以通过仅除去更多复合材料但仍保持完全相同的质数的方式来增强它们。对于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相同的效果，但是我们必须谨慎行事，以确保我们创建的滤镜与定理。

Here are some useful statistics about wheel factorization. 50% of the integers
in Nat0 are even and, other than 2, not prime. 33% of the integers in Nat0
have 3 as a prime factor and are not prime. 20% of the integers in Nat0 have 5
as a prime factor and are not prime. Collectively, 67 % of the integers in
Nat0 have prime factors of 2 or 3 and are not prime. Collectively, about 75%
of the integers in Nat0 have prime factors of 2, 3 or 5 and are not prime. A
simple method for eliminating 1/2, 2/3 or 3/4 of the integers in Nat0 from
more complex testing for being prime is very enticing and is the motive for
using wheel factorization as a preliminary filter in prime number sieves. It
is also a motivation for using values of m with an accompanying set R that can
filter all composites wtih prime factors representing large quantities of
composites.

绝对最小值是，要删除素数为2（即所有偶数）的复合材料，然后最后加2。人们至少希望去除素数为2或3的复合材料。优选地，人们想要去除素数为2、3或5的复合材料。除此之外，统计数据显示收益递减。R1的m
= 4可以达到最低要求。R1a，R2a和R3a满足m = 12时，至少要达到一个。R1b，R2b和R3b的m = 60达到了非常理想的结果。

处理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的形式可以用于第二个二次方。实际上，它是定理中第二个二次方使用的形式。如果我们使用它代替已经考虑过的示例，则可以从集合R中移除元素1的第一个二次方（当其m
= 12时）以去除重叠。

在调整算法时，必须使用尽职调查来维持定理所需的条件。在选择m的值和R的集合时，必须确保该形式是等价的，不会将定理中未通过轮分解产生的n的任何新值引入二次。

对于实现，将根据涉及数据结构，算术，处理器功能（特别是关于乘法和除法），可用的处理器缓存，内存和数据结构大小的复杂性和效率做出选择。在m的值和必须检查的集合R中的余数（残基）之间存在权衡。其中一些可能是在解释中看到m
= 60而在算法中看到m = 12的原因。这无疑是Atkin和Bernstein在其算法中使用m = 60的形式的原因。

在Atkin和Bernstein的论文中，他们还提供了使用晶格为n的特定值寻找二次方程解的算法。这些额外的算法使Atkin和Bernstein可以创建筛算法，该算法在二次和轮分解​​上同时进行过滤。在Wikipedia文章的算法中，没有考虑任何具有车轮分解因子的二次方的晶格派生解的算法。在Wikipedia文章中，对二次方程使用了详尽的x，y值技术，并且在n的二次方程返回值之后应用了轮分解。同样，这是效率问题，必须由实施者决定。