Сито Аткина - пример объяснения и Java

Ответ 1

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

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

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

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

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

{некоторый перечислимый набор или свойство, определяющее один}

для представления множества

Nat0

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

Нат

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

{символ для элемента набора: критерии, определяющие набор в терминах символа}

#

для представления заданной мощности, т.е. количества элементов в наборе

^

чтобы представить экспоненцию, т.е. квадрат, записанный как x ^ 2

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

n = (k * m) + r для k в Nat0 и r в R = {r: r в Nat0 и r < м}

n mod m = r, где r в R = {r: r в Nat0 и r < м}

Вот определения, приведенные в теоремах в их статье, а также некоторые замечания о модулярных арифметических формах:

• 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 целые числa >= 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 в {n: (Nat0 * 6) + 1}, где x и y >= 1, а n не имеет идеального квадратного фактора} нечетно. То есть, если и только если существует нечетное число (x, y) пар, которые решают квадратичное n = (3 * x ^ 2) + (y ^ 2), где x и y целые числa >= 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 целые числа, где 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 в 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 где r в R1 = {r: 1} и k в Nat0

что совпадает с записью

n mod 4 = r где r в R1 = {r: 1}

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

Для алгоритмов могут быть сделаны различные варианты для m, а при правильном множестве R свойства, указанные в теореме, сохраняются. Авторы статьи и статьи в Википедии предполагают, что читатели уже знают все это и сразу узнают об этом. Для других значений m, используемых в статье и статье в Википедии, эквиваленты:

n mod 12 = r где r в 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):

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

n = (k * 6) + r где r в R2 = {r: 1} и k в Nat0

снова это то же самое, что

n mod 6 = r где r в R2 = {r: 1}

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

Эквиваленты в статье и статье:

n mod 12 = r где r в R2a = {r: 1, 7}

n mod 60 = r, где r в R2b = {r: 1, 7, 13, 19, 25, 31, 37, 43, 49, 55}

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

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

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

n = k * 12 + r, где k в Nat0 и r в R3a = {r: 11}

Опять же, это то же самое, что:

n mod 12 = r где r в R3a = {r: 11}

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

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

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

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

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

n mod 12 = r где r в R1a = {1:1, 5} (9 имеет делитель 3, общий с 12)

n mod 60 = r где r в R1b = {r: 1, 13, 17, 29, 37, 41, 49, 53} (5, 25 и 45 имеют делитель 5, общий с 60; 9, 21, 33, 45 и 57 имеют делитель 3, общий с 60), и это форма в алгоритме в работе Аткина и Бернштейна.

Для второй квадратичной:

n mod 12 = r где r в R2a = {1, 7} (ни один из элементов R не имеет общего делителя с 12}

n mod 60 = r где r в R2b = {r: 1, 7, 13, 19, 31, 37, 43, 49} (25 и 55 имеют делитель 5, общий с 60), и это форма в алгоритм в работе Аткина и Бернштейна.

Для третьей квадратичной:

n mod 12 = r где r в R3a = {r: 11} (ни один из элементов R не имеет общего делителя с 12}

n mod 60 = 4 где r в R3b = {r: 11, 23, 47, 59} (35 имеет делитель 5, общий с 60), и это форма в алгоритме в работе Аткина и Бернштейна.

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

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

n mod 12 = r где r в R1a = {r: 1, 5} (не удалены дубликаты) (это форма, показанная в алгоритме Википедии)

n mod 60 = r, где r в R1b = {r: 1, 13, 17, 29, 37, 41, 49, 53} (без дубликатов) (это форма, показанная в объяснении Википедии)

Для второй квадратичной:

n mod 12 = r где r в R2a = {r: 7} (элемент 1 удален, поскольку он уже находится в R1a) (это форма, показанная в алгоритме Википедии)

n mod 60 = r, где r в R2b = {r: 7, 19, 31, 43} (элементы 1, 13, 37 и 49 удалены, поскольку они уже находятся в R1b) (это форма, показанная в Википедии объяснение)

Для третьей квадратичной:

n mod 12 = r где r в R3a = {r: 11} (без дубликатов)

n mod 60 = r где r в R3b = {r: 11, 23, 47, 59} (без дубликатов)

Можно задать один оставшийся вопрос о том, почему значения m варьируются от 4, 6, 12 и 60. Это связано с тем, сколько композитных (т.е. не-простых) чисел нужно исключить из более сложного тестирования для того, чтобы быть с использованием квадратичности по сравнению с сложностью используемой факторизации колес.

Значение m используется для определения того, какие композиты могут быть немедленно устранены без исключения простых чисел. Если m = 4 и R1 = {r: 1}, как и в теореме для первой квадратичности, все числа с первичными множителями из 2 устраняются, так как 1 взаимно прост ко всем числам, а 4 имеет простые множители из 2. Важно что, поскольку 3 не находится в этом наборе R, факторизация колес с использованием m = 4 и set 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 где r в R1a = {r: 1, 5}

и

n mod 6 = r, где r в R = {r: 1, 5}

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

n mod 4 = r где r в R1 = {r: 1}

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

n mod 6 = r где r в R = {r: 1}

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

n mod 12 = r где r в 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. Опять же, это проблема эффективности, которую должны решить разработчики.