вероятно, знаете) знать некоторые из основных представленных здесь идей о простых числах, составных числах и ситах, но они могут помочь другим читателям в понимании природы алгоритма. Некоторые из этих ответов опасно близки к математическому эквиваленту StackOverflow, но я чувствую, что некоторые из них необходимы для установления связи между тем, что делает алгоритм, и тем, как он это делает.

Три модульные арифметические и квадратичные пары в статье Википедии об этом сите получены из трех пар в статье Аткина и Бернштейна, в которой ядро этого сита опубликовано с помощью теорем (и их доказательств) и показывает, что они вместе образуют сито с простыми числами. Любой один даст только простые числа, но не все простые числа. Требуются все три, чтобы получить все простые числа.

Вот Java-программа, которая реализует алгоритм Википедии. Я не претендую на эффективность реализации, просто это рабочая прямая реализация в java алгоритма статьи Wikipedia.

// 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, Это плотное чтение для нематематиков и имеет всю краткость, типичную для статьи Американского математического общества.

Далее следует более глубокое объяснение того, как алгоритм получен из описания и статьи Аткина и Бернштейна.

Аткин и Бернштейн (оправданно) предполагают, что их читатели хорошо понимают сита простых чисел, модульную арифметику и факторизацию колес с использованием модульной арифметики. К сожалению, описание и алгоритм статьи в Википедии предполагают аналогичные вещи, хотя и в несколько меньшей степени. Аткин и Бернштейн не утверждают, что их три пары факторизаций колес и неприводимые квадратики являются единственными, которые могут быть использованы, и приводят примеры других пар, которые можно использовать, без дальнейших комментариев о том, как. Следовательно, три, для которых Аткин и Бернштейн дают теоремы и доказательства, являются тремя, используемыми в алгоритмах, основанных на их работе. Аткин и Бернштейн также не утверждают, что их три пары являются оптимальными. Они, видимо, удобны.

Прикольные математические символы, действительно полезные для такого рода краткого обсуждения, здесь недоступны. Для целей этого ответа я буду использовать

{ some enumerated set or property that defines one }

представлять набор

Nat0

представлять множество натуральных чисел, включая ноль, то есть Nat0 = {0, 1, 2, ...},

Nat

представлять набор натуральных чисел, не включающий ноль, то есть Nat = {1, 2, 3, ...} и следующую конструкцию для определения набора и символа для его элемента:

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

#

для представления множества элементов, то есть количества элементов в наборе

^

для обозначения возведения в степень, то есть х в квадрате, записанного как х ^ 2

Модульная арифметика, используемая в факторизациях колес в описаниях, теоремах и алгоритмах, представлена в двух эквивалентных формах:

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

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

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

Свойство факторизации колес, которое, как предполагают читатели в статье и статье в Википедии, хорошо известно читателю, состоит в том, что модульная арифметика может использоваться для выборочного выбора только целых чисел, которые не имеют определенных простых факторов. В виде

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

если выбрать только те элементы R, которые являются относительно простыми по отношению к m, то все целые числа n, которые удовлетворяют выражению, будут либо простым числом, либо относительно простым числом по отношению к m.

m относительно простого числа n означает, что у них нет общего целочисленного делителя & gt; 1. Примеры относительно простых чисел: 2 - относительно простое число для 3, 4 - относительно простое число для 9, 9 - относительно простое число для 14. Понимание этого важно для понимания остатков (остатков), используемых в модульной арифметике, и того, как они эквивалентны в различных версиях объяснений и алгоритмов.

Далее будет объяснено, как связаны все теоремы, алгоритмы и объяснения.

Для первого квадратичного n = (4 * x ^ 2) + (y ^ 2):

Теорема использует форму:

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

что то же самое, что писать

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

Обратите внимание, что он определяет n как любое другое нечетное число в Nat0, начиная с 1, т.е. {1, 5, 9, 13, ...}.

Для алгоритмов можно сделать различные выборы для 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}

Некоторые элементы в наборах R1a и R1b могут быть удалены по двум причинам, объясненным позже, и теорема все еще будет применяться.

Для второго квадратичного n = (3 * x ^ 2) + (y ^ 2):

Теорема использует форму:

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

опять же это так же, как

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

Обратите внимание, что это каждое третье нечетное число в Nat0, начиная с 1, то есть {1, 7, 13, 19, ...}

Эквивалентами в статье и статье являются:

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}

Снова, значения в наборах R2a и R2b могут быть удалены по двум причинам, объясненным позже, и теорема все еще будет применяться.

Для третьего квадратичного (3 * x ^ 2) - (y ^ 2):

Теорема использует форму:

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

Опять же, это так же, как:

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

Обратите внимание, что это каждое шестое нечетное число в Nat0, начиная с 11, то есть {11, 23, 35, 47, ...}

Эквивалентами в статье и статье являются:

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

Опять же, значение в наборе R3b может быть удалено по причине, объясненной позже, и теорема все еще будет применяться.

В различных алгоритмах и объяснениях для значений m = 12 и m = 60 элементы множеств R удаляются, не влияя на справедливость теоремы или алгоритмов. Есть две причины, по которым некоторые значения в множествах R могут быть отброшены.

Первая причина состоит в том, что любое значение r в множестве R, которое не является относительно простым для m, с которым оно спарено, будет служить только для включения значений для n, которые являются составными целыми числами с одним или несколькими простыми множителями m, ни одно из которых будут простые числа. Эта особенность модульной арифметики заключается в том, что факторизации колес используются для фильтрации большого количества не простых чисел из дальнейших тестов, обычно более сложных и менее эффективных, для определения, являются ли они простыми. В этом сите более сложный тест состоит в том, является ли число решений конкретной неприводимой квадратичной нечетным числом. Это означает, что мы можем немедленно отбросить все значения в наборе R для этого алгоритма, которые не являются относительно простыми к значению m, используемому с этим множеством R.

Вторая причина заключается в том, что в статье факторизации колес создают наборы целых чисел, которые перекрываются, включая перекрывающиеся простые числа. В то время как они были удобны, и перекрытие не имело значения для теорем, в алгоритме это расточительно, если его можно легко избежать. В этом случае это тривиально избежать. Кроме того, если множество целых чисел из факторизаций колеса перекрывается, то нечетное число решений в одной квадратике плюс нечетное число решений в другой квадратике станет кумулятивным четным числом решений (нечетное число плюс нечетное число ВСЕГДА четное число). Во многих реализациях, включая реализацию Википедии, это идентифицирует простое число как не простое, поскольку реализации, такие как Википедия 1, определяют первичность из совокупных решений для всех квадратичных и не выделяют решения из каждой квадратичной. В этих случаях обязательно, чтобы целые числа из факторизаций колес были исключительными подмножествами целых чисел.

Реализация не хочет проверять одно и то же число более чем в одном квадратике, если в этом нет необходимости, и это не так. Значение для r в множестве R, используемом в трех квадратиках, при условии, что используется один и тот же m, должно быть только в одном из них. Если оно в более чем одном, то одно и то же значение для n будет отображаться более одного раза и тестироваться с более чем одним квадратиком. При использовании одного и того же значения m обеспечение того, что один и тот же элемент R не отображается в R более чем для одного квадратичного, устранит перекрытие. В случае статьи в Википедии, перекрытие, предотвращаемое факторизацией колеса, предотвращает ошибочные результаты, которые могут возникнуть с кумулятивными квадратичными решениями, которые в одном квадрате нечетны, но в двух квадратиках накапливаются до четного числа.

Другой алгоритм может избежать наложения перед вычислением квадратичных значений. В эмпирических тестах квадратиков и факторизаций колес факторизации колес, где m = 12, дают значительно меньше значений для n, чем будут решать квадратики. Использование факторизации колес, где m = 60, значительно увеличивает разницу. Если бы алгоритм квадратичного решения для конкретных значений n был высокоэффективным, то можно было бы значительно улучшить использование только значений, полученных из факторизаций колес, для тестирования квадратиков.

Вот факторизации колес после удаления элементов, которые не являются относительно простыми. Для первого квадратичного:

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

Обратите внимание, что некоторые из одинаковых элементов появляются в наборах R1a и R2a для первого и второго квадратиков. То же самое верно для множеств R1b и R2b. Когда m равно 12, набор общих элементов равен {1}; когда m равно 60, набор общих элементов равен {1, 13, 37, 49}. Обеспечение включения элемента R только для одного квадратичного создает следующие формы, которые вы теперь должны распознать из статьи Википедии.

Для первого квадратичного:

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 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 where r in R3a = {r: 11} (no duplicates)

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

Один оставшийся вопрос может быть задан относительно того, почему значения 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 и набором R2, который не содержит 5, большое число простых чисел, возможно, половина из них, будет исключено.

Если m = 12 и R3 = {r: 11}, как в теореме для третьего квадратичного, все составные числа с простыми множителями 2 или 3 исключаются, потому что 11 относительно простых относительно 12, а 12 имеет простые множители 2 и 3. Опять же, с m = 12 и установленным R3, который не содержит 1, 5 или 7, большое число простых чисел, возможно, намного больше половины, будет исключено.

Одна из вещей, которые Аткин и Бернштейн неофициально показывают в своей статье, заключается в том, что, хотя коэффициенты колеса в теоремах индивидуально исключают простые числа из их соответствующих квадратиков, в совокупности три факторизации колеса допускают все простые числа, а в случае факторизации колеса в первый и второй квадратики допускают значительное перекрытие. Хотя они не устраняют перекрытие в своих алгоритмах, где 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, но мы должны проявить осторожность, чтобы то, что мы создаем, было эквивалентно тем, которые используются в теоремы.

Вот некоторые полезные статистические данные о факторизации колес. 50% целых чисел в Nat0 четные и, кроме 2, не простые. 33% целых чисел в Nat0 имеют 3 как главный фактор и не являются простыми. 20% целых чисел в Nat0 имеют 5 как главный фактор и не являются простыми. В совокупности 67% целых чисел в Nat0 имеют простые множители 2 или 3 и не являются простыми. В совокупности около 75% целых чисел в Nat0 имеют простые множители 2, 3 или 5 и не являются простыми. Простой метод исключения 1/2, 2/3 или 3/4 целых чисел в Nat0 из более сложного тестирования на простое число очень заманчив и является причиной использования факторизации колес в качестве предварительного фильтра в ситах простых чисел. Это также мотивация для использования значений m с сопровождающим набором 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 where r in R1a = {r : 1, 5}

а также

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

потому что форма, где m = 6 не эквивалентна

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

Обратите внимание, что:

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

эквивалентно

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

и форма, где m = 6 может использоваться со вторым квадратиком. На самом деле это форма, используемая со вторым квадратиком в теореме. Если бы мы использовали его вместо уже рассмотренных примеров, мы могли бы удалить элемент 1 из множества R для первого квадратичного, когда его m = 12, чтобы убрать перекрытие.

При корректировке алгоритма должная осмотрительность должна использоваться для поддержания условий, которые требуют теоремы. При выборе значений для m и наборов для R необходимо убедиться, что форма является эквивалентной и не вводит никаких новых значений для n в квадратик, которые не были получены факторизацией колеса в теореме.

Для реализаций выбор делается на основе сложностей и эффективности, включающих структуры данных, арифметику, возможности процессора (особенно в отношении умножения и деления), доступный кэш процессора, память и размер структур данных. Есть компромиссы между значениями m и количеством остатков (остатков) в наборах R, которые необходимо проверить. Некоторые из них могут быть причинами для того, чтобы видеть m = 60 в объяснении и m = 12 в алгоритме. Это определенно причины, по которым Аткин и Бернштейн использовали формы с m = 60 в алгоритмах в своей статье.

В работе Аткина и Бернштейна они также предоставляют алгоритмы для нахождения решений квадратиков для конкретных значений n с использованием решеток. Эти дополнительные алгоритмы позволили Аткину и Бернштейну создать ситовые алгоритмы, которые фильтровали одновременно по квадратикам и факторизации колеса. Ни один из алгоритмов для решеточных решений квадратиков с факторизациями колес не рассматривался в алгоритме статьи Википедии. В статье Википедии исчерпывающий метод значений x, y используется с квадратиками, а факторизации колес применяются после того, как квадратики возвращают значения для n. Опять же, это проблема эффективности, которую должны решать исполнители.