Sieb von Atkin Erklärung

Question

Ich mache gerade ein Projekt und brauche eine effiziente Methode zur Berechnung von Primzahlen. Ich habe die sieve of Eratosthenes verwendet, aber ich habe herum gesucht und gefunden, dass die sieve of Atkin eine effizientere Methode ist. Ich fand es schwierig, eine Erklärung für diese Methode zu finden (die ich verstehen konnte!). Wie funktioniert es? Beispielcode (vorzugsweise in C oder Python) wäre genial.

Edit: danke für Ihre Hilfe, die einzige Sache, die ich immer noch nicht verstehe, ist, was die x- und y-Variablen im Pseudocode beziehen. Könnte jemand bitte für mich etwas Licht darauf werfen?

Answer 1

Der wiki page ist immer ein guter Startpunkt, da er den Algorithmus vollständig erklärt und einen kommentierten Pseudocode liefert. (NB Es gibt viele Details, und da die Wiki Webseite zuverlässig nach oben ist, werde ich es hier nicht zitieren.)

Für Referenzen in den spezifischen Sprachen, die Sie erwähnt:

• C implementation (optimiert)
• Python implementation

Hoffnung, das hilft.

Answer 2

Hier ist eine C++ Implementierung von Sieb von Atkin, die Ihnen helfen könnte ...

#include <iostream> 
#include <cmath> 
#include <fstream> 
#include<stdio.h> 
#include<conio.h> 
using namespace std; 

#define limit 1000000 

int root = (int)ceil(sqrt(limit)); 
bool sieve[limit]; 
int primes[(limit/2)+1]; 

int main (int argc, char* argv[]) 
{ 
    //Create the various different variables required 
    FILE *fp=fopen("primes.txt","w"); 
    int insert = 2; 
    primes[0] = 2; 
    primes[1] = 3; 
    for (int z = 0; z < limit; z++) sieve[z] = false; //Not all compilers have false as the  default boolean value 
    for (int x = 1; x <= root; x++) 
    { 
     for (int y = 1; y <= root; y++) 
     { 
      //Main part of Sieve of Atkin 
      int n = (4*x*x)+(y*y); 
      if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true; 
      n = (3*x*x)+(y*y); 
      if (n <= limit && n % 12 == 7) sieve[n] ^= true; 
      n = (3*x*x)-(y*y); 
      if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true; 
     } 
    } 
     //Mark all multiples of squares as non-prime 
    for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false; 
    //Add into prime array 
    for (int a = 5; a < limit; a++) 
    { 
      if (sieve[a]) 
      { 
        primes[insert] = a; 
        insert++; 
      } 
    } 
    //The following code just writes the array to a file 
    for(int i=0;i<1000;i++){ 
      fprintf(fp,"%d",primes[i]); 
      fprintf(fp,", "); 
    } 

    return 0; 
} 

Answer 3

Edit: das einzige, was ich immer noch nicht verstehe ist, was die Variablen x und y beziehen sich auf in der Pseudocode. Könnte jemand bitte für mich etwas Licht darauf werfen?

Für eine grundlegende Erklärung der gemeinsamen Nutzung des ‚x‘ und ‚y‘ Variablen in der Wikipedia-Seite Pseudo-Code (oder eine anderen besseren Implementierungen des Sieb des Atkin), könnten Sie my answer to another related question hilfreich.

Answer 4

// Title : Seive of Atkin (Prime number Generator) 

#include <iostream> 
#include <cmath> 
#include <vector> 

using namespace std; 

int main() 
{ 
    ios_base::sync_with_stdio(false); 
    long long int n; 
    cout<<"Enter the value of n : "; 
    cin>>n; 
    vector<bool> is_prime(n+1); 
    for(long long int i = 5; i <= n; i++) 
    { 
     is_prime[i] = false; 
    } 
    long long int lim = ceil(sqrt(n)); 

    for(long long int x = 1; x <= lim; x++) 
    { 
     for(long long int y = 1; y <= lim; y++) 
     { 
      long long int num = (4*x*x+y*y); 
      if(num <= n && (num % 12 == 1 || num%12 == 5)) 
      { 
       is_prime[num] = true; 
      } 

      num = (3*x*x + y*y); 
      if(num <= n && (num % 12 == 7)) 
      { 
       is_prime[num] = true; 
      } 

      if(x > y) 
      { 
       num = (3*x*x - y*y); 
       if(num <= n && (num % 12 == 11)) 
       { 
        is_prime[num] = true; 
       } 
      } 
     } 
    } 
    // Eliminating the composite by seiveing 
    for(long long int i = 5; i <= lim; i++) 
    { 
     if(is_prime[i]) 
      for(long long int j = i*i; j <= n; j += i) 
      { 
       is_prime[j] = false; 
      } 
    } 
    // Here we will start printing of prime number 
    if(n > 2) 
    { 
     cout<<"2\t"<<"3\t"; 
    } 
    for(long long int i = 5; i <= n; i++) 
    { 
     if(is_prime[i]) 
     { 
      cout<<i<<"\t"; 
     } 
    } 
    cout<<"\n"; 
    return 0; 
} 

Answer 5

Wikipedia article hat eine Erklärung:

• „Der Algorithmus völlig ignoriert alle Zahlen teilbar durch zwei, drei oder fünf alle Zahlen mit einem noch Modulo-sechzig Rest durch zwei teilbar und nicht. prime. Alle Zahlen mit modulo-sechzig Rest, die durch drei teilbar sind, sind ebenfalls durch drei und nicht durch Primzahl teilbar. Alle Zahlen mit modulo-sechzig Rest durch fünf teilbar sind teilbar durch fünf und nicht prim. Alle diese Reste werden ignoriert.

Beginnen wir mit dem berühmten

primes = sieve [2..] = sieve (2:[3..]) 
    -- primes are sieve of list of 2,3,4... , i.e. 2 prepended to 3,4,5... 
sieve (x:xs) = x : sieve [y | y <- xs, rem y x /= 0] -- set notation 
    -- sieve of list of (x prepended to xs) is x prepended to the sieve of 
    --     list of `y`s where y is drawn from xs and y % x /= 0 

Mal sehen, beginnen, wie es für ein paar erste Schritte fort:

primes = sieve [2..] = sieve (2:[3..]) 
        = 2 : sieve p2  -- list starting w/ 2, the rest is (sieve p2) 
p2 = [y | y <- [3..], rem y 2 /= 0]  -- for y from 3 step 1: if y%2 /= 0: yield y 

p2 ist keine Vielfachen von enthalten.IOW es wird nur Zahlen Cofrime mit — keine Nummer in p2 hat als seinen Faktor. Für p2 brauchen wir nicht wirklich teilen zu testen, indem jede Zahl in [3..] (das ist und höher, 3,4,5,6,7, ...), weil wir alle aufzählen das Vielfachen von im Voraus:

rem y 2 /= 0 === not (ordElem y [2,4..])  -- "y is not one of 2,4,6,8,10,..." 

ordElem ist wie elem (dh ist Element Test), ist es nur annimmt dass seine Liste Argument ist eine geordnete, zunehmende Liste von Nummern, so dass es kann das Nicht-Vorhandensein s erkennen afely sowie Präsenz:

ordElem y xs = take 1 (dropWhile (< y) xs) == [y] -- = elem y (takeWhile (<= y) xs) 

Der gewöhnliche elem übernimmt nichts, so muss jedes Element der Liste Argument untersuchen, so kann nicht unendlich Listen handhaben. ordElem kann. Also dann,

p2 = [y | y <- [3..], not (ordElem y [2,4..])] -- abstract this as a function `diff`: 
    = diff [3..] [2,4..]    -- diff ys xs = [y | y <- ys, not (ordElem y xs)] 
    -- 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
    -- . 4 . 6 . 8 . 10 . 12 . 14 . 16 . 18 . 20 . 22 . 
    = diff [3..] (map (2*) [2..])   -- y > 2, so [4,6..] is enough 
    = diff [2*k+x | k <- [0..], x <- [3,4]] -- "for k from 0 step 1: for x in [3,4]: 
      [2*k+x | k <- [0..], x <- [ 4]] --       yield (2*k+x)" 
    = [  2*k+x | k <- [0..], x <- [3 ]]     -- 2 = 1*2 = 2*1 
    = [3,5..]            -- that's 3,5,7,9,11,... 

p2 ist nur eine Liste aller Gewinnchancen über . Nun, wir wussten dass. Was ist mit dem nächsten Schritt?

sieve p2 = sieve [3,5..] = sieve (3:[5,7..]) 
         = 3 : sieve p3 
p3 = [y | y <- [5,7..], rem y 3 /= 0] 
    = [y | y <- [5,7..], not (ordElem y [3,6..])]   -- 3,6,9,12,... 
    = diff [5,7..] [6,9..]   -- but, we've already removed the multiples of 2, (!) 
    -- 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 
    -- . 6 . . 9 . . 12 . . 15 . . 18 . . 21 . . 24 . . 27 . 
    = diff [5,7..] (map (3*) [3,5..])      -- so, [9,15..] is enough 
    = diff [2*k+x | k <- [0..], x <- [5]] (map (3*) 
      [2*k+x | k <- [0..], x <- [3]]) 
    = diff [6*k+x | k <- [0..], x <- [5,7,9]]    -- 6 = 2*3 = 3*2 
      [6*k+x | k <- [0..], x <- [ 9]] 
    = [  6*k+x | k <- [0..], x <- [5,7 ]]    -- 5,7,11,13,17,19,... 

Und die nächste,

sieve p3 = sieve (5 : [6*k+x | k <- [0..], x <- [7,11]]) 
     = 5 : sieve p5 
p5 = [y | y <-  [6*k+x | k <- [0..], x <- [7,11]], rem y 5 /= 0] 
    = diff [ 6*k+x | k <- [0..], x <- [7,11]] (map (5*) 
      [ 6*k+x | k <- [0..], x <- [5, 7]] )     -- no mults of 2 or 3! 
    = diff [30*k+x | k <- [0..], x <- [7,11,13,17,19,23,25,29,31,35]] -- 30 = 6*5 = 5*6 
      [30*k+x | k <- [0..], x <- [     25,  35]] 
    = [  30*k+x | k <- [0..], x <- [7,11,13,17,19,23, 29,31 ]] 

Dies ist die Reihenfolge, mit der das Sieb des Atkin arbeitet. Es sind keine Vielfachen von 2, 3 oder darin vorhanden. Atkin und Bernstein arbeiten Modulo , das heißt, sie doppelte Reichweite:

p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]] 

Als nächste sie einige anspruchsvollen Sätze verwenden, um einige Eigenschaften von jedem dieser Zahlen kennen und mit jedem entsprechend zu behandeln. Das Ganze wird wiederholt (a-la das "Rad") mit einer Periode von .

• „alle Zahlen n mit Modulo-Rest sechzig 1, 13, 17, 29, 37, 41, 49 oder 53 (...) sind prime, wenn und nur wenn die Anzahl von Lösungen für 4x^2 + y^2 = n ist ungerade und die Zahl ist quadratisch. "

Was bedeutet das? Wenn wir wissen, dass die Anzahl der Lösungen für diese Gleichung für eine solche Zahl ungerade ist, dann ist es prime wenn es ist quadratisch. Das heißt, es hat keine wiederholten Faktoren (wie 49, 121, usw.).

Atkin und Bernstein nutzen diese die Anzahl der Operationen insgesamt zu reduzieren: für jede Primzahl (von und höher), aufzuzählen wir (und Markierung für die Entfernung) das Vielfachen von seinen Platz, so dass sie viel weiter anders als im Sieb von Eratosthenes, so gibt es weniger von ihnen in einem bestimmten Bereich.

Der Rest der Regeln sind:

• „Alle Zahlen n mit Modulo-Rest sechzig 7, 19, 31, oder 43 (...) sind prime, wenn und nur wenn die Anzahl der Lösungen zu 3x^2 + y^2 = n ist ungerade und die Zahl ist quadratisch. "

• „Alle Zahlen n mit Modulo-sechzig Rest 11, 23, 47 oder 59 (...) ist prime, wenn und nur wenn die Anzahl von Lösungen für 3x^2 − y^2 = n ungerade ist und die Zahl ist quadrat.“

Diese kümmert sich um alle 16 Kernzahlen in der Definition von p60.

siehe auch: Which is the fastest algorithm to find prime numbers?

---

die Zeitkomplexität des Siebes von Eratosthenes in der Herstellung von Primzahlen bis N ist O (N log N log), während die des Siebes von Atkin ist O (N) (abgesehen von den zusätzlichen log log N Optimierungen, die nicht gut skalieren). Die akzeptierte Weisheit ist jedoch, dass die konstanten Faktoren im Sieb von Atkin viel höher sind und sich daher nur über die 32-Bit-Zahlen auszahlen könnten (N> 2), if at all.