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

Вы можете (и, вероятно, знаете) некоторые из основных идей, приведенных здесь, о простых числах, составных числах и решетах, но они могут помочь другим читателям понять природу алгоритма. Некоторые из этих ответов опасно близки к принадлежности к математическому эквиваленту 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 в квадрате записывается как x ^ 2

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

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

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

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

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), где 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.

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

Реализация не хочет проверять одно и то же число более чем в одном квадратичном, если в этом нет необходимости, и это не так. Значение 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 и набора R1 также исключит большое количество простых чисел, возможно, половину из них.

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

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