Sieve of Atkin - Wyjaśnienie i przykład Javy

Question

Przeczytałem o Sieve of Atkin na Wikipedii, ale wiki jest w tej chwili ograniczone. Szukałem wyjaśnienia Sieve of Atkin na wysokim poziomie i przykład w Javie.

Dzięki.

Answer 1

Można (i prawdopodobnie można) znać niektóre z podstawowych idei tutaj podanych o liczbach pierwszych, liczbach zespolonych i sitach, ale mogą one przynieść korzyści innym czytelnikom w zrozumieniu natury algorytmu. Niektóre z tych odpowiedzi niebezpiecznie zbliżają się do przynależności do matematycznego odpowiednika StackOverflow, ale czuję, że niektóre z nich są konieczne, aby utworzyć połączenie między tym, co robi algorytm i jak to robi.

Trzy modułowe pary arytemetyczne i kwadratowe w artykule Wikipedii na temat tego sita pochodzą z trzech par w artykule Atkina i Bernsteina, które opublikowały rdzeń tego sita z twierdzeniami (i ich dowodami) i pokazują, że wspólnie tworzą one sito liczb pierwszych. Każdy z osobna przyniesie tylko liczby pierwsze, ale nie da wszystkich liczb pierwszych. Potrzeba wszystkich trzech, aby uzyskać wszystkie liczby pierwsze.

Oto program java, który implementuje algorytm Wikipedii. Nie twierdzę, że chodzi o efektywność implementacji, tylko że jest to działająca bezpośrednia implementacja w java algorytmu artykułu Wikipedii.

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

mam kopii (współautorem Bernstein) oryginalnego papieru Atkin w którym opisano twierdzenia, z którego sito jest zbudowane. Ten artykuł jest dostępny tutaj: http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf. Jest to gęste czytanie dla nie-matematyków i ma całą zwięzłość typową dla amerykańskiego papieru matematycznego.

Poniżej znajduje się głębsze wyjaśnienie, w jaki sposób algorytm wywodzi się z opisu i artykułu Atkina i Bernsteina.

Atkin i Bernstein (słusznie) zakładają, że ich czytelnicy dokładnie rozumieją sita liczb pierwszych, modułową arytmetykę i faktoryzację koła za pomocą modularnej arytmetyki. Niestety, opis i algorytm artykułu w Wikipedii zakładają podobne rzeczy, choć w nieco mniejszym stopniu. Atkin i Bernstein nie twierdzą, że ich trzy pary współczynników koła i nieredukowalne kwadryty są jedynymi, które można zastosować, i podać przykłady innych par, których można użyć bez dalszego komentarza. Stąd te trzy, dla których Atkin i Bernstein dają twierdzenia i dowody, to trzy stosowane w algorytmach opartych na ich pracy. Atkin i Bernstein również nie twierdzą, że ich trzy pary są optymalne. Są najwyraźniej wygodne.

Funkcjonalne symbole matematyczne przydatne w tego rodzaju dyskusji w zwięzły sposób nie są dostępne tutaj. Dla celów niniejszej odpowiedzi, będę używał

{pewnych wymienionych zestaw lub właściwość, która określa jeden}

do reprezentowania zestaw

Nat0

do reprezentuje zbiór liczb naturalnych, w tym zero, tj. Nat0 = {0, 1, 2, ...}

Nat

reprezentuje zbiór liczb naturalnych, nie licząc jako zero, tj Nat = {1, 2, 3, ...} i że poniższy definiowania zestawu i i symbolem elementu go:

{symbol elementu zestawu: kryteria który definiuje zestaw w kategoriach symbolu}

#

do reprezentowania ustawić liczność, czyli liczbę elementów w zestawie

^

do reprezentowania potęgowanie, czyli x kwadrat zapisać jako x^2

Modułowa arytmetycznej używane w rozkładach koła w opisach, twierdzenia i algorytmy pojawiają się w dwóch równoważnych postaciach:

n = (k * m) + r dla k w Nat0 i r in R = {r: r w Nat0 i r < m.}

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

Oto definicje podane w twierdzeń w swojej pracy wraz z kilkoma Uwagi o modułowych form arytmetycznych:

1. n wynosi zawsze pierwsza gdzie # {(x, y): n = (4 * x^2) + (y^2), n in {n: (Nat0 * 4) + 1}, gdzie x i y> = 1 i n nie ma idealnego współczynnika kwadratowego} jest nieparzyste . To znaczy, jeśli i tylko jeśli istnieje nieparzysta liczba par (x, y), które rozwiązują kwadratowe n = (4 * x^2) + (y^2), gdzie x i y są liczbami całkowitymi> = 1, n mod 4 = 1 i n nie ma doskonałych czynników kwadratowych, a n jest liczbą pierwszą. Zauważ tutaj, że forma n mod m = r, gdzie r jest w R ma m = 4, a R = {r: 1}.

2. n jest zawsze pierwsze, gdzie # {(x, y): n = (3 * x^2) + (y^2), n w {n: (Nat0 * 6) + 1}, gdzie x a y> = 1, a n nie ma idealnego pola kwadratowego} jest nieparzyste. To znaczy, jeśli i tylko jeśli istnieje nieparzysta liczba par (x, y), które rozwiązują kwadrat n = (3 * x^2) + (y^2) gdzie x i y są liczbami całkowitymi> = 1, n mod 6 = 1 i n nie ma doskonałych czynników kwadratowych, a n jest liczbą pierwszą. Zauważ tutaj, że forma n mod m = r, gdzie r jest w zbiorze R, ma m = 6 i R = {r: 1}.

3. n jest zawsze pierwsze, gdzie # {(x, y): n = (3 * x^2) - (y^2), {n: (Nat0 * 12) + 11}, x> y> = 1 i n nie ma idealnego pola kwadratowego} jest nieparzyste. To znaczy, jeśli i tylko jeśli istnieje nieparzysta liczba par (x, y), które rozwiązują kwadratowe n = (3 * x^2) - (y^2), gdzie x, y są liczbami całkowitymi, gdzie x> y> = 1 , n mod 12 = 11 i n nie ma doskonałych czynników kwadratowych, a n jest liczbą pierwszą. Zauważ tutaj, że forma n mod m = r, gdzie r jest w zbiorze R, ma m = 12 i R = {r: 11}.

Właściwość factorizations kół, że papier i artykuł Wikipedia zakładających czytelnik wie dobrze, że arytmetyka modularna może być stosowany do selektywnego wyboru tylko liczby całkowite, które nie mają pewnych czynników pierwszych.W postaci

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

jeśli wybiera tylko elementy R, który jest względnie pierwsze dla M, a następnie wszystkie liczby całkowite, które spełniają wyrażenie, będą albo liczbą pierwszą, albo względną liczbą pierwszą do m.

m względnie pierwsza n oznacza, że ​​nie mają one wspólnego dzielnika całkowitoliczbowego> 1. Przykłady liczb względnych pierwszych to: 2 to względnie pierwsza do 3, 4 to względnie pierwsza do 9, 9 to względnie pierwsza do 14. Zrozumienie tego jest niezbędne do zrozumienia reszty (pozostałości) używanych w modułowej arytmetyki oraz tego, jak są one równoważne w różnych wersjach wyjaśnień i algorytmów.

Poniżej wyjaśniono, w jaki sposób wiążą się twierdzenia, algorytmy i wyjaśnienia.

W pierwszym kwadratowej n = (4 * x^2) + (R^2)

Twierdzenie wykorzystuje postać:

n = (K * 4) + R gdzie r r1 = r {1}, a k w Nat0

który jest taki sam jak pisanie

n mod 4 = r, gdzie r w R1 = R {1}

Należy zauważyć, że definiuje on n jako każdą inną nieparzystą liczbę w Nat0, począwszy od 1, tj. {1, 5, 9, 13, ...}.

Dla algorytmów można dokonać różnych wyborów dla m, a przy odpowiednim ustawieniu R, właściwości pokazane przez twierdzenie zachowane. Autorzy artykułu z artykułu w Wikipedii zakładają, że czytelnicy już to wszystko znają i natychmiast to rozpoznają. Dla innych wartości m, stosowane w wyrobie papierowym i Wikipedia, odpowiedniki są:

n mod 12 = r, gdzie r w R1a = {r: 1, 5, 9}

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

Pewne elementy w zestawy R1a i R1b mogą zostać usunięte z dwóch powodów wyjaśnionych później, a twierdzenie będzie nadal obowiązywało.

Dla drugiego kwadratowej n = (3 * x^2) + (R^2)

Twierdzenie wykorzystuje postać:

n = (K * 6) + R w którym R {= R2 r: 1} i K w Nat0

znów jest taka sama jak

mod n = 6, gdzie R w R2 = R {1}

Uwaga tutaj, że to co trzecia liczba nieparzysta w Nat0 począwszy od 1, czyli {1, 7, 13, 19, ...}

Odpowiedniki w papierze i artykuł:

n mod 12 = r, gdzie r w R2a = {r: 1, 7}

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

Ponownie, wartości w zestawach R2a i R2b mogą zostać usunięte z dwóch powodów wyjaśnionych później, a twierdzenie będzie nadal obowiązywało.

W trzecim kwadratowej (3 * x^2) - (R^2)

Twierdzenie wykorzystuje postać:

n = K * 12 + R, w których k w Nat0 i R w R3a = {r: 11}

Ponownie, jest taka sama, jak:

mod n = 12, gdzie R w R3a = {r: 11}

Uwaga tutaj, że to co szósty nieparzysta w Nat0 zaczynając od 11, to znaczy {11, 23, 35, 47, ...}

Odpowiedniki n papier i artykuł:

n mod 60 = r, gdzie r w R3b = {r: 11, 23, 35, 47, 59}

Ponownie, wartości zadanej R3b można usunąć z tego powodu wyjaśnione później twierdzenie nadal będzie obowiązywać.

W różnych algorytmach i objaśnieniach, dla wartości m = 12 im = 60, elementy zbiorów R są usuwane bez wpływu na ważność twierdzenia lub algorytmów. Istnieją dwa powody, dla których niektóre wartości w zestawach R mogą zostać odrzucone.

Pierwszym powodem jest to, że każda wartość r w zbiorze R, która nie jest względnie pierwsza w m, z którą jest parowana, posłuży tylko do wprowadzenia wartości n, które są liczbami całkowitymi zespolonymi z jednym lub większą liczbą czynników pierwszych m , z których żadna nie będzie liczbą pierwszą.Ta cecha modułowej arytmetyki powoduje, że współczynniki koła są wykorzystywane do odfiltrowywania dużych ilości liczb innych niż prime z dalszych testów, zwykle bardziej złożonych i mniej wydajnych, niezależnie od tego, czy są one pierwszymi. Na tym sicie bardziej złożonym testem jest to, czy liczba rozwiązań konkretnego nieredukowalnego kwadratu jest liczbą nieparzystą. Oznacza to, że możemy natychmiast odrzucić wszystkie wartości w zbiorze R dla tego algorytmu, który nie jest pełniejszy od wartości m używanej z tym zbiorem R.

Drugi powód jest taki, że w artykule współczynniki koła tworzą zestawy liczby całkowite, które się nakładają, w tym nakładające się liczby pierwsze. Podczas gdy były one wygodne i nakładanie się nie miało znaczenia dla twierdzeń, w algorytmie jest to marnotrawstwo, jeśli można go łatwo uniknąć. W tym przypadku jest to banalnie unikane. Ponadto, jeśli zbiór liczb całkowitych z rozkładów kołowych pokrywa się, wówczas nieparzysta liczba rozwiązań w jednym kwadraty plus nieparzysta liczba rozwiązań w innym kwadratowym stanie się kumulatywną, nawet liczbą rozwiązań (nieparzysta liczba plus nieparzysta liczba to ZAWSZE Liczba parzysta). W wielu implementacjach, w tym w implementacji Wikipedii, będzie to oznaczać liczbę pierwszą jako nie pierwszą, ponieważ implementacje, takie jak Wikipedia, unieruchamiają pierwotność rozwiązań kumulacyjnych dla wszystkich kwadratów i nie segregują rozwiązań z każdego kwadratu. W tych przypadkach konieczne jest, aby liczby całkowite z faktoryzacji kół były wyłącznymi podzbiorami liczb całkowitych.

Implementacja nie chce testować tej samej liczby w więcej niż jednym kwadracie, jeśli nie jest to konieczne, a tak nie jest. Wartość r w zbiorze R użytym w trzech kwadratach, przy założeniu, że jest używany ten sam m, musi być tylko w jednym z nich. Jeśli jest w więcej niż jednym, to ta sama wartość dla n pojawi się więcej niż raz i zostanie przetestowana z więcej niż jedną kwadratową. Dla tej samej wartości mw użyciu, zapewnienie, że ten sam element R nie pojawi się w R dla więcej niż jednego kwadratu, wyeliminuje nakładanie się. W przypadku artykułu w Wikipedii, nakładanie się, któremu zapobiegnie fakt faktoryzacji koła, zapobiega błędnym wynikom, które wystąpiłyby w przypadku kumulatywnych rozwiązań quadrytycznych, które w pojedynczym kwadracie są nieparzyste, ale w dwóch kwadrykach, kumulują się do liczby parzystej.

Inny algorytm może uniknąć nakładania się przed obliczeniem kwadratów. W testach empirycznych quadratyków i rozkładów kołowych współczynniki koła, w których m = 12 dają znacznie mniejszą wartość niż n, rozwiążą zagadnienie kwadratowe. Stosowanie współczynników kołowych, gdzie m = 60, znacznie zwiększa różnicę. Jeśli kwadratowy algorytm rozwiązania dla określonych wartości n byłby bardzo wydajny, wówczas może nastąpić znaczna poprawa poprzez zastosowanie tylko wartości, które pochodzą z faktoryzacji koła w celu przetestowania quadratics.

Tutaj są współczynniki koła po usunięciu elementów, które nie są względnie pierwsze. Dla pierwszego kwadratu:

n mod 12 = r, gdzie r w R1a = {1: 1, 5}, (9 zawiera dzielnik 3 wspólnych z 12)

n mod 60 = r, gdzie r w R1b = {r: 1, 13, 17, 29, 37, 41, 49, 53} (5, 25 i 45 mają dzielnik 5 wspólny z 60; 9, 21, 33, 45 i 57 mają dzielnik 3 wspólny z 60) i to jest forma w algorytmie w artykule Atkina i Bernsteina.

Dla drugiego kwadratu:

n mod 12 = r, gdzie r w R2a = {1, 7} (bez elementem R ma dzielnik wspólnych z 12}

n mod 60 = r gdzie r w R2b = {r: 1, 7, 13, 19, 31, 37, 43, 49} (25 i 55 mają dzielnik 5 wspólny z 60) i jest to postać w algorytmie w Atkin i Papier Bernstein.

Dla trzeciego kwadratu:

n mod 12 = r, gdzie r in R3a = {r: 11} (bez elementem R ma dzielnik wspólnych z 12}

n mod 60 = 4, w którym R w R3b = {r: 11, 23, 47, 59}. (35 zawiera dzielnik 5 wspólnych z 60), i jest to postać w algorytmie w papierze Atkin Bernsteina

Wskazówki niektóre z tych samych elementów pojawiają się w zestawach R1a i R2a dla pierwszego i drugiego kwadryty. To samo dotyczy zestawów R1b i R2b. Gdy m wynosi 12, zbiorem wspólnych elementów jest {1}; gdy m wynosi 60, zbiór wspólnych elementów to {1, 13, 37, 49}. Zapewnienie, że element R zostanie uwzględniony tylko dla jednego kwadratowego, tworzy następujące formy, które powinieneś teraz rozpoznać z artykułu Wikipedii.

W pierwszym kwadratowa:

n mod 12 = r, gdzie r w R1a = {r: 1, 5} (duplikaty usunięte) (to jest w postaci pokazanej na algorytmie Wikipedia)

n mod 60 = r gdzie r w R1b = {r: 1, 13, 17, 29, 37, 41, 49, 53} (bez duplikatów usuniętych) (jest to forma przedstawiona w objaśnieniu Wikipedii)

Dla drugiego kwadratu:

n mod 12 = r, gdzie r w R2a = {r: 7} (1 Element usunięty, gdyż jest już w R1a) (to jest w postaci pokazanej na algorytmie Wikipedia)

n mod 60 = R gdzie r w R2b = {r: 7, 19, 31, 43} (elementy 1, 13, 37 i 49 usunięte, ponieważ są już w R1b) (jest to forma przedstawiona w objaśnieniu Wikipedii)

W przypadku trzeciego kwadratu:

n mod 12 = r gdzie r w R3a = {r: 11} (brak duplikatów)

n mod 60 = r, gdzie r w R3b = {r: 11, 23, 47, 59} (duplikaty)

pozostająca kwestia może być, dlaczego wartości m zakres, 4, 6, 12 i 60. Dotyczy to liczby złożonych (tj inne niż pierwsze) liczby, które chce się wykluczyć z bardziej złożonych testów na pierwsze użycie przy użyciu quadratics w porównaniu do złożoności zastosowanej faktoryzacji koła.

Wartość m używana może określać, które kompozyty mogą zostać natychmiast wyeliminowane bez eliminowania liczb pierwszych. Jeśli m = 4 i R1 = {r: 1}, tak jak w twierdzeniu dla pierwszego kwadratu, wszystkie liczby z czynnikami pierwszymi 2 zostaną wyeliminowane, ponieważ 1 jest względnie pierwsze dla wszystkich liczb, a 4 ma czynniki pierwsze o 2. Jest to ważne aby zauważyć, że ponieważ 3 nie znajduje się w tym zbiorze R, faktoryzacja koła za pomocą m = 4 i ustawienie R1 również wykluczy dużą liczbę liczb pierwszych, być może połowę z nich.

Jeśli m = 6 i R2 = {r: 1} jak w twierdzeniu dla drugiego kwadratu, wszystkie liczby zespolone z czynnikami pierwszymi 2 lub 3 zostają wyeliminowane, ponieważ 1 jest względnie pierwsze dla wszystkich liczb, a 6 ma czynniki pierwsze z 2 i 3.Ponownie, przy m = 6 i ustawieniu R2, który nie zawiera 5, duża liczba liczb pierwszych, może połowa z nich, zostanie wykluczona.

Jeśli m = 12 i R3 = {r: 11} jak w twierdzeniu dla trzeciego kwadratu, wszystkie złożone mumbers z czynnikami pierwszymi 2 lub 3 zostają wyeliminowane, ponieważ 11 jest względnie pierwsze do 12, a 12 ma czynniki pierwsze 2 i 3. Ponownie, przy m = 12 i zbiorze R3, który nie zawiera 1, 5 lub 7, duża liczba liczb pierwszych, być może więcej niż połowa z nich, zostanie wykluczona.

Jedną z rzeczy, które Atkin i Bernstein nieformalnie wykazują w swoich artykułach, jest to, że chociaż współczynniki kół w twierdzeniach indywidualnie wykluczają liczby pierwsze z ich odpowiednich kwadratów, zbiorowo, trzykrotne rozróżnienia zezwalają na wszystkie liczby pierwsze, a w przypadku współczynniki tarcia kół w pierwszym i drugim kwadryty pozwalają na znaczne nakładanie się. Chociaż nie usuwają nakładania się w swoich algorytmach, gdzie m = 60, artykuł w Wikipedii ma miejsce, gdzie ustawiają m = 12 w algorytmie artykułu, a m = 60 w objaśnieniu artykułu.

Dla kwadratów Atkina i Bernsteina użytych w ich twierdzeniach, osłabienie współczynników koła, które z nimi idą, unieważni ich działanie zgodnie z twierdzeniami. Możemy jednak wzmocnić je w sposób, który usuwa tylko więcej kompozytów, ale nadal zachowuje dokładnie te same liczby pierwsze. Dla formularzy, w których m = 4, (4 = 2 * 2) każda nawet całkowita liczba zostanie przefiltrowana. W przypadku formularzy, w których m = 12 (12 = 2 * 2 * 3), każda liczba całkowita z czynnikami pierwszymi 2 lub 3 zostaje przefiltrowana. W przypadku formularzy, w których m = 60 (60 = 2 * 2 * 3 * 5), każda liczba całkowita z czynnikami pierwszymi 2, 3 lub 5 zostaje przefiltrowana. Moglibyśmy użyć potencjalnie filtrów o m = 6 dla tego samego efektu co m = 12 i m = 30 dla tego samego efektu co m = 60, ale musielibyśmy uważać, aby to, co tworzymy, było równoważne z tymi używanymi w twierdzenia.

Oto kilka użytecznych statystyk dotyczących faktoryzacji koła. 50% liczb całkowitych w Nat0 jest równych i, innych niż 2, nie jest liczbą pierwszą. 33% liczb całkowitych w Nat0 ma 3 jako czynnik główny i nie jest liczbą pierwszą. 20% liczb całkowitych w Nat0 ma 5 jako czynnik główny i nie jest liczbą pierwszą. Łącznie 67% liczb całkowitych w Nat0 ma czynniki pierwsze 2 lub 3 i nie jest liczbą pierwszą. Łącznie około 75% liczb całkowitych w Nat0 ma czynniki pierwsze rzędu 2, 3 lub 5 i nie jest liczbą pierwszą. Prosta metoda eliminowania 1/2, 2/3 lub 3/4 liczb całkowitych w Nat0 z bardziej złożonych testów na bycie pierwszą jest bardzo kusząca i jest motywem do zastosowania faktoryzacji koła jako filtra wstępnego w sitach z liczbami pierwszych. Jest to również motywacja do stosowania wartości mz towarzyszącym zestawem R, który może filtrować wszystkie kompozyty z czynnikami pierwiastkowymi reprezentującymi duże ilości kompozytów.

Jako absolutne minimum należałoby usunąć kompozyty o współczynniku głównym 2 (tj. Wszystkie liczby parzyste), a następnie dodać 2 z powrotem na końcu. Można by przynajmniej chcieć usunąć kompozyty o czynnikach pierwszorzędowych 2 lub 3. Korzystnie, chciałoby się usunąć kompozyty z czynnikami pierwszymi 2, 3 lub 5. Po tym, statystyki pokazują malejące zyski. m = 4 z R1 osiąga absolutne minimum. m = 12 z R1a, R2a i R3a osiąga najmniej jeden chciałby. m = 60 z R1b, R2b i R3b osiąga bardzo pożądany wynik.

Jest kilka rzeczy do rozważenia przy pracy z wartościami dla m i ustawia R.Należy pamiętać, że te dwie formy nie są równoważne w pierwszym kwadratowa:

n mod 12 = r, gdzie r w R1a = {r: 1, 5}

i

6 mod n, w którym R = R w R R = {1, 5}

ponieważ forma, w którym m = 6 nie odpowiada

n mod 4 = r, gdzie r r1 = {r: 1}

zauważyć, że:

n mod 6 = R, w którym R w R = {r: 1}

odpowiada

mod n = 12, gdzie R w R = {r: 1, 7}

i formularza, w którym m = 6 może być używany z drugim kwadratem. Jest to w rzeczywistości forma użyta z drugim kwadratem w twierdzeniu. Gdybyśmy używali go zamiast przykładów już rozważonych, moglibyśmy usunąć element 1 z zestawu R dla pierwszego kwadratu, gdy jego m = 12, aby usunąć nakładanie.

Przy dostosowywaniu algorytmu należy zachować należytą staranność, aby zachować warunki wymagane przez twierdzenia. Wybierając wartości dla m i zbiorów dla R, należy upewnić się, że forma jest równoważna, która nie wprowadza żadnych nowych wartości n do kwadratów, które nie zostały wytworzone przez faktoryzację koła w twierdzeniu.

W przypadku wdrożeń dokonywane są wybory w oparciu o złożoność i efektywność obejmującą struktury danych, arytmetykę, możliwości procesora (zwłaszcza w odniesieniu do mnożenia i dzielenia), dostępną pamięć podręczną procesora, pamięć i rozmiar struktur danych. Istnieją różnice między wartościami m i liczbą pozostałości (pozostałości) w zestawach R, które należy sprawdzić. Niektóre z nich mogą być powodem, dla których m = 60 w wyjaśnieniu i m = 12 w algorytmie. Są to bezsprzecznie powody, dla których Atkin i Bernstein stosowali formy o m = 60 w algorytmach w ich pracy.

W gazecie Atkin and Bernstein dostarczają również algorytmy do znajdowania rozwiązań dla quadratics dla konkretnych wartości n za pomocą sieci. Te dodatkowe algorytmy pozwoliły Atkinowi i Bernsteinowi stworzyć algorytmy przesiewania, które filtrowały jednocześnie na kwadrykach i rozkładach koła. Żaden z algorytmów rozwiązań opartych na sieci dla kwadratów z rozróżnianiem kół nie został uwzględniony w algorytmie artykułu z Wikipedii. W artykule z Wikipedii używa się wyczerpującej techniki wartości x, y z kwadratami, a współczynniki koła są stosowane po kwadratach zwracających wartości dla n. Ponownie, jest to kwestia efektywności, o której decydują realizatorzy.