Sieve of Atkin - 解释和 Java 示例

Sieve of Atkin - Explanation and Java example

提问by Jash Sayani

I have read about Sieve of Atkin on Wikipedia but the wiki is limited at the moment. I was looking for an explanation of Sieve of Atkin at a high level and an example in Java.

我在维基百科上读过关于阿特金筛法的内容，但目前维基是有限的。我一直在寻找对阿特金筛法的高层次解释和 Java 示例。

Thanks.

谢谢。

回答by Jim

You may (and probably do) know some of the basic ideas given here about prime numbers, composite numbers and sieves, but they may benefit other readers in understanding the nature of the algorithm. Some of this answer gets dangerously close to belonging on the math equivalent of StackOverflow, but I feel some of it is necessary to make the connection between what the algorithm does and how it does it.

您可能（也可能确实）知道这里给出的一些关于素数、合数和筛法的基本思想，但它们可能有助于其他读者理解算法的本质。这个答案中的一些非常接近于属于 StackOverflow 的数学等价物，但我觉得有必要在算法的作用和它的工作方式之间建立联系。

The three modular arithemetic and quadratic pairs in the Wikipedia article on this sieve are derived from the three pairs in the Atkin and Bernstein paper that published the core of this sieve with theorems (and their proofs) and show they collectively form a prime number sieve. Any one alone will yield only prime numbers, but will not yield all prime numbers. It takes all three to yield all prime numbers.

这个筛子的维基百科文章中的三个模算术和二次对源自 Atkin 和 Bernstein 论文中的三个对，该论文用定理（及其证明）发表了这个筛子的核心，并表明它们共同构成了一个素数筛子。任何一个人都只会产生质数，但不会产生所有质数。需要所有三个才能产生所有质数。

Here is a java program that implements the Wikipedia algorithm. I make no claims about implementation efficiency, just that it is a working direct implementation in java of the Wikipedia article algorithm.

这是一个实现维基百科算法的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

I have a copy of Atkin's (co-authored with Bernstein) original paper in which he describes the theorems from which the sieve is constructed. That paper is available here: http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf. It's dense reading for non-mathematicians and has all the conciseness typical of an American Mathematical Society paper.

我有一份阿特金（与伯恩斯坦合着）的原始论文，他在其中描述了构建筛子的定理。该论文可在此处获得：http: //www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf。对于非数学家来说，这是一本密集的读物，并且具有美国数学学会论文的所有典型简洁性。

What follows here is a deeper explanation of how the algorithm is derived from the description and the paper from Atkin and Bernstein.

下面是对算法如何从 Atkin 和 Bernstein 的描述和论文中推导出来的更深入的解释。

Atkin and Bernstein (justifiably) assume their readers thoroughly understand prime number sieves, modular arithmetic and wheel factorization using modular arithmetic. Unfortunately, the Wikipedia article description and algorithm assume similar things, although to slightly lesser degree. Atkin and Bernstein make no claim that their three pairs of wheel factorizations and irreducible quadratics are the only ones that could be used and give passing examples of other pairs that could be used with no further comment on how. Hence, the three for which Atkin and Bernstein give theorems and proofs are the three used in algorithms based on their work. Atkin and Bernstein also make no claim that their three pairs are optimal ones. They are, apparently, convenient ones.

Atkin 和 Bernstein（合理地）假设他们的读者完全理解素数筛、模算术和使用模算术的轮因式分解。不幸的是，维基百科的文章描述和算法假设了类似的东西，尽管程度略低。Atkin 和 Bernstein 没有声称他们的三对轮分解和不可约二次方程是唯一可以使用的，并且给出了可以使用的其他对的示例，没有进一步评论如何使用。因此，阿特金和伯恩斯坦给出定理和证明的三个是基于他们的工作在算法中使用的三个。Atkin 和 Bernstein 也没有声称他们的三对是最佳的。显然，它们是方便的。

The funky math symbols really useful for this kind of discussion in a concise way are not available here. For the purposes of this answer, I will use

此处没有以简洁的方式对此类讨论真正有用的时髦数学符号。出于此答案的目的，我将使用

{ some enumerated set or property that defines one }

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

to represent a set

代表一个集合

Nat0

NAT0

to represent the set of natural numbers including zero, i.e., Nat0 = {0, 1, 2, ...},

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

Nat

纳特

to represent the set of natural numbers not including zero, i.e. , Nat = {1, 2, 3, ...} and the following construct for defining a set and and a symbol for an element of it:

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

{symbol for element of a set : criteria that defines the set in terms of the symbol}

#

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

#

to represent set cardinality, i.e. the number of elements in a set

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

^

^

to represent exponentiation, i.e. x squared written as x^2

表示求幂，即 x 平方写成 x^2

The modular arithmetic used in the wheel factorizations in descriptions, theorems and algorithms appears in two equivalent forms:

在描述、定理和算法的轮因式分解中使用的模算术以两种等价形式出现：

n = (k * m) + r for k in Nat0 and r in R = {r : r in Nat0 and r < m}

n mod m = r where r in R = {r : r in Nat0 and r < m}

n = (k * m) + r for k in Nat0 and r in R = {r : r in Nat0 and r < m}

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

Here are the definitions given in the theorems in their paper along with some notes about the modular arithmetic forms:

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

1. n is always prime where #{(x, y) : n = (4 * x^2 )+ (y^2), n in {n : (Nat0 * 4) + 1}, where x and y >= 1 and n has no perfect square factor} is odd. That is, if and only if there are an odd number of (x, y) pairs that solve the quadratic n = (4 * x^2) + (y^2) where x and y integers >= 1, n mod 4 = 1 and n has no perfect square factors, then n is prime. Note here that the form n mod m = r where r is in R has m = 4 and R = {r : 1}.

2. n is always prime where #{(x, y) : n = (3 * x^2) + (y^2), n in {n : (Nat0 * 6) + 1}, where x and y >= 1 and n has no perfect square factor} is odd. That is, if and only if there are an odd number of (x, y) pairs that solve the quadratic n = (3 * x^2) + (y^2) where x and y integers >= 1, n mod 6 = 1 and n has no perfect square factors, then n is prime. Note here that the form n mod m = r where r is in set R has m = 6 and R = {r : 1}.

3. n is always prime where #{(x, y) : n = (3 * x^2) - (y^2), {n : (Nat0 * 12) + 11}, x > y >= 1 and n has no perfect square factor} is odd. That is, if and only if there are an odd number of (x, y) pairs that solve the quadratic n = (3 * x^2) - (y^2) where x , y integers where x > y >= 1, n mod 12 = 11 and n has no perfect square factors, then n is prime. Note here that the form n mod m = r where r is in set R has m = 12 and R = {r : 11}.

1. 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}。

2. 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}。

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) where x , y integers where x > y >= 1 , n mod 12 = 11 且 n 没有完全平方因数，则 n 是素数。注意这里的形式 n mod m = r 其中 r 在集合 R 中有 m = 12 和 R = {r : 11}。

A property of wheel factorizations that the paper and the Wikipedia article assume the reader knows well is that modular arithmetic can be used to selectively choose only integers that don't have certain prime factors. In the form

这篇论文和维基百科文章假设读者非常了解轮因式分解的一个属性是，模算术可用于选择性地仅选择不具有某些质因数的整数。在形式

n mod m = r, r in R = {r : Nat0, r < m},

n mod m = r, r in R = {r : Nat0, r < m},

if one chooses only elements of R that are relatively prime to m, then all integers n that satisfy the expression will either be a prime number or relatively prime to m.

如果只选择 R 中与 m 互质的元素，则所有满足表达式的整数 n 要么是质数，要么与 m 互质。

m relatively prime to n means they have no common integer divisor > 1. Examples of relatively prime numbers are: 2 is relatively prime to 3, 4 is relatively prime to 9, 9 is relatively prime to 14. Understanding this is essential to understanding the remainders (residues) used in the modular arithmetic and how they are equivalent in the various versions of the explanations and algorithms.

m 与 n 互质意味着它们没有公整数除数 > 1。互质数的例子是：2 与 3 互质，4 与 9 互质，9 与 14 互质。理解这一点对于理解模算术中使用的余数（残差）以及它们在各种版本的解释和算法中的等效性。

The following will now explain how the theorems, algorithms and explanations all relate.

下面将解释这些定理、算法和解释之间的关系。

For the first quadratic, n = (4 * x^2) + (y^2):

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

The theorem uses the form:

该定理使用以下形式：

n = (k * 4) + r where r in R1 = {r : 1} and k in Nat0

n = (k * 4) + r 其中 R1 中的 r = {r : 1} 和 Nat0 中的 k

which is the same as writing

这和写作一样

n mod 4 = r where r in R1 = {r : 1}

n mod 4 = r 其中 R1 中的 r = {r : 1}

Note that it defines n as having to be every other odd number in Nat0 starting from 1, i.e. {1, 5, 9, 13, ...}.

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

For algorithms, various choices for m can be made and, with the right set R, the properties shown by the theorem preserved. The authors of the paper and Wikipedia article assume the readers already know all of this and will immediately recognize it. For the other values of m used in the paper and Wikipedia article, the equivalents are:

对于算法，可以对 m 进行各种选择，并且在正确的集合 R 下，定理显示的属性得以保留。这篇论文和维基百科文章的作者假设读者已经知道所有这些并且会立即认出它。对于论文和维基百科文章中使用的其他 m 值，等效项是：

n mod 12 = r where r in R1a = {r : 1, 5, 9}

n mod 60 = r where r in R1b = {r : 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57}

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}

Certain elements in the sets R1a and R1b can get removed for two reasons explained later and the theorem will still apply.

集合 R1a 和 R1b 中的某些元素可以被删除，原因有两个，稍后解释，该定理仍然适用。

For the second quadratic, n = (3 * x^2) + (y^2):

对于第二个二次方程，n = (3 * x^2) + (y^2)：

The theorem uses the form:

该定理使用以下形式：

n = (k * 6) + r where r in R2 = {r : 1} and k in Nat0

n = (k * 6) + r 其中 R2 中的 r = {r : 1} 和 Nat0 中的 k

again this is the same as

这又是一样的

n mod 6 = r where r in R2 = {r : 1}

n mod 6 = r 其中 R2 中的 r = {r : 1}

Note here that this is every third odd number in Nat0 starting from 1, i.e. {1, 7, 13, 19, ...}

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

Equivalents in the paper and article are:

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

n mod 12 = r where r in R2a = {r : 1, 7}

n mod 60 = r where r in R2b = {r : 1, 7, 13, 19, 25, 31, 37, 43, 49, 55}

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}

Again, values in a sets R2a and R2b can get removed for two reasons explained later and the theorem will still apply.

同样，集合 R2a 和 R2b 中的值可以被删除，原因有两个，稍后解释，该定理仍然适用。

For the third quadratic, (3 * x^2) - (y^2):

对于第三次二次方，(3 * x^2) - (y^2)：

The theorem uses the form:

该定理使用以下形式：

n = k * 12 + r where k in Nat0 and r in R3a = {r : 11}

n = k * 12 + r 其中 Nat0 中的 k 和 R3a 中的 r = {r : 11}

Again, this is the same as:

同样，这与以下内容相同：

n mod 12 = r where r in R3a = {r : 11}

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

Note here that this is every sixth odd number in Nat0 starting from 11, i.e. {11, 23, 35, 47, ...}

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

Equivalents n the paper and article are:

论文和文章的等价物是：

n mod 60 = r where r in R3b = {r : 11, 23, 35, 47, 59}

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

Again, a value in set R3b can be removed for a reason explained later and the theorem will still apply.

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

In the various algorithms and explanations, for values of m = 12 and m = 60, elements of sets R get removed without affecting the validity of the theorem or the algorithms. There are two reasons that some values in sets R can get discarded.

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

The first reason is that any value of r in a set R that is not relatively prime to the m with which it is paired will serve only to incude values for n that are composite integers with one or more prime factors of m, none of which will be prime numbers. This feature of modular arithmetic is why wheel factorizations are used to filter out large quantities of non-prime numbers from further tests, usually more complex and less efficient ones, for whether they are prime. In this sieve, the more complex test is whether the number of solutions to a specific irreducible quadratic is an odd number. That means we can immediately discard all values in the set R for this algorithm that is not releatively prime to the value of m being used with that set R.

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

The second reason is that in the paper, the wheel factorizations create sets of integers that overlap, including overlapping primes. While they were convenient and the overlap didn't matter for the theorems, in an algorithm it is wasteful if it can be easily avoided. In this case, it is trivially avoided. Also, if the set of integers from the wheel factorizations overlap, then an odd number of solutions in one quadratic plus an odd number of solutions in another quadratic will become a cummulative even number of solutions (an odd number plus an odd number is ALWAYS an even number). In many implementations, including the Wikipedia implementation, this will identify a prime number as not being prime since implementations like the Wikipedia one detrmine primality from cummulative solutions for all the quadratics and don't segregate solutions from each quadratic. In those cases it is imperative that the integers from the wheel factorizations be exclusive subsets of integers.

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

An implementation does not want to test the same number in more than one quadratic if that is not necessary, and it isn't. A value for r in a set R used in the three quadratics, assuming the same m is being used, need be in only one of them. If it is in more than one, then the same value for n will show up more than once and get tested with more than one quadratic. For the same value of m in use, ensuring that the same element of R doesn't show up in the R for more than one quadratic will eliminate the overlap. In the case of the Wikipedia article, the overlap prevented by the wheel factorization prevents erroneous results that would occur with cummulative quadritic solutions that, in a single quadratic are odd, but in two quadratics, accumulate to an even number.

如果没有必要，实现不希望在一个以上的二次方中测试相同的数字，而事实并非如此。在三个二次方程中使用的集合 R 中的 r 值，假设使用相同的 m，只需在其中一个中。如果它在多个中，那么 n 的相同值将出现不止一次，并用多个二次方进行测试。对于使用的相同 m 值，确保 R 的相同元素不会出现在 R 中超过一个二次方将消除重叠。在维基百科文章的情况下，轮分解防止的重叠防止了累积二次解会出现的错误结果，在单个二次方中为奇数，但在两个二次方中累积为偶数。

A different algorithm might avoid overlap before calculating the quadratics. In empirical tests of the quadratics, and wheel factorizations, the wheel factorizations where m = 12 yield significantly fewer values for n than than will solve the quadratics. Using wheel factorizations where m = 60 increases the difference significantly. If a quadratic solution algorithm for specific values of n were highly efficient, then there could be a significant improvement by using only values that come from the wheel factorizations for testing the quadratics.

在计算二次方程之前，不同的算法可能会避免重叠。在二次方程和车轮分解的经验测试中，当 m = 12 时，车轮分解产生的 n 值明显少于求解二次方程的值。使用 m = 60 的轮子分解会显着增加差异。如果针对特定 n 值的二次求解算法非常有效，那么通过仅使用来自轮因式分解的值来测试二次方程可能会有显着的改进。

Here are the wheel factorizations after removing elements that are not relatively prime. For the first quadratic:

以下是去除非素数元素后的轮因式分解。对于第一个二次方：

n mod 12 = r where r in R1a = {1 : 1, 5} (9 has divisor 3 common with 12)

n mod 60 = r where r in R1b = { r : 1, 13, 17, 29, 37, 41, 49, 53} (5, 25 and 45 have divisor 5 common with 60; 9, 21, 33, 45 and 57 have divisor 3 common with 60) and this is the form in the algorithm in the Atkin and Bernstein paper.

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 的除数 5 与 60 相同；9, 21, 33, 45 和57 的除数 3 与 60 相同），这是 Atkin 和 Bernstein 论文中算法的形式。

For the second quadratic:

对于第二次二次方：

n mod 12 = r where r in R2a = {1, 7} (no element of R has a divisor common with 12}

n mod 60 = r where r in R2b = {r : 1, 7, 13, 19, 31, 37, 43, 49} (25 and 55 have divisor 5 common with 60) and this is the form in the algorithm in the Atkin and Bernstein paper.

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 与 60 有除数 5），这是算法中的形式阿特金和伯恩斯坦论文。

For the third quadratic:

对于第三次二次方：

n mod 12 = r where r in R3a = {r : 11} ( no element of R has a divisor common with 12}

n mod 60 = 4 where r in R3b = {r : 11, 23, 47, 59} (35 has divisor 5 common with 60) and this is the form in the algorithm in the Atkin and Bernstein paper.

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 论文中算法的形式。

Notice that some of the same elements show up in the sets R1a and R2a for the first and second quadratics. The same is true for sets R1b and R2b. When m is 12, the set of common elements is {1}; when m is 60 the set of common elements is {1, 13, 37, 49}. Ensuring that an element of R gets included for only one quadratic creates the following forms that you should now recognize from the Wikipedia article.

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

For the first quadratic:

对于第一个二次方：

n mod 12 = r where r in R1a = {r : 1, 5} (no duplicates removed) (this is the form shown in the Wikipedia algorithm)

n mod 60 = r where r in R1b = {r : 1, 13, 17, 29, 37, 41, 49, 53} (no duplicates removed) (this is the form shown in the Wikipedia explanation)

n mod 12 = r 其中 R1a 中的 r = {r : 1, 5}（没有删除重复项）（这是维基百科算法中显示的形式）

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

For the second quadratic:

对于第二次二次方：

n mod 12 = r where r in R2a = {r : 7} (element 1 removed since it is already in R1a) (this is the form shown in the Wikipedia algorithm)

n mod 60 = r where r in R2b = {r : 7, 19, 31, 43} (elements 1, 13, 37 and 49 removed since they are already in R1b) (this is the form shown in the Wikipedia explanation)

n mod 12 = r 其中 r in R2a = {r : 7} （删除元素 1 因为它已经在 R1a 中）（这是维基百科算法中显示的形式）

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

For the third quadratic:

对于第三次二次方：

n mod 12 = r where r in R3a = {r: 11} (no duplicates)

n mod 60 = r where r in R3b = {r: 11, 23, 47, 59} (no duplicates)

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

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

One remaining question might be made as to why values of m range over 4, 6, 12 and 60. This has to do with how many composite (i.e. non-prime) numbers one wants to exclude from more complex testing for being prime using the quadratics versus the complexity of the wheel factorization used.

剩下的一个问题可能是为什么 m 的值范围超过 4、6、12 和 60。这与人们想要从更复杂的质数测试中排除多少个合数（即非质数）有关，使用二次方程与使用的轮分解的复杂性。

The value for m used can determine which composites can get immediately eliminated without eliminating primes. If m = 4 and R1 = {r : 1}, as in the theorem for the first quadratic, all numbers with prime factors of 2 get eliminated because 1 is relatively prime to all numbers and 4 has prime factors of 2. It is important to note that because 3 is not in this set R, a wheel factorization using m = 4 and set R1 will also exclude a large number of primes, perhaps half of them.

使用的 m 值可以确定哪些组合可以在不消除素数的情况下立即消除。如果 m = 4 且 R1 = {r : 1}，如第一个二次方程的定理，所有质因数为 2 的数都会被消除，因为 1 对所有数都是素数，而 4 的质因数为 2。这很重要需要注意的是，因为 3 不在这个集合 R 中，使用 m = 4 和集合 R1 的轮分解也会排除大量素数，也许是其中的一半。

If m = 6 and R2 = {r : 1} as in the theorem for the second quadratic, all composite numbers with prime factors of 2 or 3 get eliminated because 1 is relatively prime to all numbers and 6 has prime factors of 2 and 3. Again, with m = 6 and set R2, which doesn't contain 5, a large number of primes, perhaps half of them, will get excluded.

如果 m = 6 且 R2 = {r : 1} 如第二次二次方程的定理，则所有质因数为 2 或 3 的合数都会被消除，因为 1 对所有数都是素数，而 6 的质因数为 2 和 3 . 再一次，当 m = 6 且集合 R2 不包含 5 时，大量素数，可能是其中的一半，将被排除在外。

If m = 12 and R3 = {r : 11} as in the theorem for the third quadratic, all composite mumbers with prime factors of 2 or 3 get eliminated because 11 is relatively prime to 12 and 12 has prime factors of 2 and 3. Again, with m = 12 and set R3, which doesn't contain 1, 5 or 7, a large number of primes, perhaps well more than half of them, will get excluded.

如果 m = 12 且 R3 = {r : 11} 如第三次二次定理中的定理，则所有质因数为 2 或 3 的合数都会被消除，因为 11 与 12 互质，而 12 的质因数为 2 和 3。同样，当 m = 12 且集合 R3 不包含 1、5 或 7 时，大量素数（可能超过其中的一半）将被排除在外。

One of the things that Atkin and Bernstein informally show in their paper is that, although the wheel factors in the theorems individually exclude primes from their respective quadratics, collectively, the three wheel factorizations permit all primes and, in the case of the wheel factorizations in the first and second quadratics, permit significant overlap. Although they don't remove the overlap in their algorithms where m = 60, the Wikipedia article does where they set m = 12 in the article algorithm and m = 60 in the article explanation.

阿特金和伯恩斯坦在他们的论文中非正式地表明的一件事是，尽管定理中的轮因数单独从各自的二次方程中排除素数，但三轮因式分解允许所有素数，在轮因式分解的情况下第一次和第二次二次方程允许显着重叠。虽然他们没有在他们的算法中去除 m = 60 的重叠，但维基百科文章在他们在文章算法中设置 m = 12 并且在文章解释中设置 m = 60 的地方做了。

For the quadratics Atkin and Bernstein used in their theorems, weakening the wheel factorizations that go with them will invalidate that they will operate according to the theorems. However, we can strengthen them in ways that remove only more composites but still keeping the exact same primes. For the forms where m = 4, (4 = 2 * 2) every even integer gets filtered. For the forms where m = 12 (12 = 2 * 2 * 3), every integer with prime factors of 2 or 3 gets filtered. For the forms where m = 60 (60 = 2 * 2 * 3 * 5), every integer with prime factors of 2, 3 or 5 gets filtered. We could use potentially use filters with m = 6 for the same effect as m = 12 and m = 30 for the same effect as m = 60, but we would have to exercise care that what we create is equivalent to the ones used in the theorems.

对于阿特金和伯恩斯坦在他们的定理中使用的二次方程，削弱与他们一起使用的轮因式分解将使他们无法根据定理进行运算。但是，我们可以通过仅移除更多复合物但仍保持完全相同的素数的方式来增强它们。对于 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.

这里有一些关于轮子分解的有用统计数据。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 一起使用的动机，该集合可以过滤所有具有代表大量复合材料的素因子的复合材料。

As an absolute minimum, one would want to remove composites with a prime factor of 2 (i.e. all even numbers) and then add 2 back at the end. One would at least like to remove composites with prime factors of 2 or 3. Preferably, one would like to remove composites with prime factors of 2, 3 or 5. Past that, the statistics show diminishing returns. m = 4 with R1 accomplishes the bare minimum. m = 12 with R1a, R2a and R3a accomplishes the least one would like. m = 60 with R1b, R2b and R3b accomplish a very desirable result.

作为绝对最小值，人们希望删除质因数为 2（即所有偶数）的复合物，然后在最后加回 2。人们至少希望去除质因数为 2 或 3 的复合物。优选地，人们希望去除质因数为 2、3 或 5 的复合物。除此之外，统计数据显示收益递减。m = 4 且 R1 达到最低限度。m = 12 用 R1a、R2a 和 R3a 完成至少一个想要的。m = 60，R1b、R2b 和 R3b 实现了非常理想的结果。

There are some more things to consider in working with values for m and sets R. Take note that the two forms are NOT equivalent for the first quadratic:

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

n mod 12 = r where r in R1a = {r : 1, 5}

n mod 12 = r 其中 R1a 中的 r = {r : 1, 5}

and

和

n mod 6 = r where r in R = {r : 1, 5}

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

because the form where m = 6 is not equivalent to

因为 m = 6 的形式不等于

n mod 4 = r where r in R1 = {r : 1}

n mod 4 = r 其中 R1 中的 r = {r : 1}

Note that:

注意：

n mod 6 = r where r in R = {r : 1}

n mod 6 = r 其中 R 中的 r = {r : 1}

is equivalent to

相当于

n mod 12 = r where r in R = {r : 1, 7}

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

and the form where m = 6 could be used with the second quadratic. It is, in fact, the form used with the second quadratic in the theorem. If we were to use it instead of the examples already considered, we could remove the element 1 from the set R for first quadratic when its m = 12 to remove overlap.

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

In adjusting the algorithm, due diligence must be used to maintain the conditions that the theorems require. When choosing values for m and sets for R, one must ensure that the form is an equivalent one that does not introduce any new values for n to the quadratic that were not produced by the wheel factorization in the theorem.

在调整算法时，必须尽职尽责来维护定理所需的条件。在为 m 选择值并为 R 设置集合时，必须确保该形式是一种等效形式，不会将 n 的任何新值引入二次方程，这些值不是由定理中的轮因式分解产生的。

For implementations, choices get made based on complexities and efficiencies involving the data structures, arithmetic, processor capabilities (especially with regard to multiplication and division), available processor cache, memory and the size of data structures. There are tradeoffs betweeen the values for m and the number of remainders (residues) in sets R that have to be checked. Some of these may be reasons for seeing m = 60 in the explanation and m = 12 in the algorithm. They are defninitely the reasons Atkin and Bernstein used forms with m = 60 in the algorithms in their paper.

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

In the Atkin and Bernstein paper, they also provide algorithms for finding solutions to the quadratics for specific values of n using lattices. These additional algorithms allowed Atkin and Bernstein to create sieve algorithms that filtered simultaneously on the quadratics and the wheel factorizations. None of the algorithms for lattice derived solutions to the quadratics with the wheel factorizations were considered in the Wikipedia article's algorithm. In the Wikipedia article, an exhaustive x, y value technique is used with the quadratics and the wheel factorizations are applied after the quadratics return values for n. Again, this is an efficiency issue that has to be decided by implementers.

在 Atkin 和 Bernstein 的论文中，他们还提供了使用格子为特定 n 值寻找二次方程解的算法。这些额外的算法允许阿特金和伯恩斯坦创建筛选算法，同时对二次方程和轮因式分解进行过滤。在维基百科文章的算法中，没有考虑任何用于具有轮因式分解的二次方程的点阵派生解的算法。在维基百科文章中，详尽的 x, y 值技术与二次方程一起使用，并且在二次方程返回 n 值之后应用轮因式分解。同样，这是一个必须由实施者决定的效率问题。