Sieve d'explication Atkin

Question

Je fais un projet en ce moment et j'ai besoin d'une méthode efficace pour calculer les nombres premiers. J'ai utilisé le sieve of Eratosthenes mais, j'ai cherché autour et ai trouvé que le sieve of Atkin est une méthode plus efficace. J'ai trouvé difficile de trouver une explication (que j'ai pu comprendre!) De cette méthode. Comment ça marche? Exemple de code (de préférence en C ou python) serait brillant.

Éditez: merci pour votre aide, la seule chose que je ne comprends toujours pas est ce que les variables x et y se réfèrent dans le pseudo-code. Quelqu'un pourrait-il nous éclairer là-dessus?

Answer 1

Le wiki page est toujours un bon point de départ, car il explique l'algorithme dans son intégralité et fournit un pseudocode commenté. (NB Il y a beaucoup de détails, et depuis le site wiki est fiable, je ne citerai pas ici.)

Pour les références dans les langues spécifiques que vous avez mentionnés:

• C implementation (optimisé)
• Python implementation

espoir qui aide.

Answer 2

Voici un C++ mise en œuvre de Crible d'Atkin qui pourraient vous aider ...

#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: la seule chose que je ne comprends toujours pas ce que les variables x et y font référence dans le pseudo code. Quelqu'un pourrait-il nous éclairer là-dessus?

Pour une explication de base de l'utilisation commune des « x » et les variables de « y » dans le pseudo-code de la page Wikipedia (ou d'autres meilleures implémentations du Crible d'Atkin), vous trouverez peut-être my answer to another related question utile.

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 a une explication:

• « L'algorithme ne tient aucun compte des nombres divisibles par deux, trois ou cinq Tous les numéros avec un même reste modulo soixante sont divisible par deux et non. Tous les nombres avec modulo-soixante reste divisible par trois sont également divisibles par trois et non premiers Tous les nombres avec modulo-soixante reste divisible par cinq sont divisibles par cinq et non premier Tous ces restes sont ignorés. "

Commençons par la célèbre

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 

Voyons voir comment il procède pour quelques premiers pas:

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 doit contenir aucun multiple de .IOW il ne contiendra que des nombres coprime avec — aucun numéro dans p2 a comme son facteur. Pour trouver p2 nous ne devons pas vraiment tester diviser par 2 chaque numéro dans [3..] (c'est et plus, 3,4,5,6,7, ...), parce que nous pouvons énumérer tous les multiples de à l'avance:

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

ordElem est comme elem (c.-à-est-élément test), il suffit suppose que son argument de liste est une ordonnée, liste croissante de nombres, de sorte qu'il peut détecter la non-présence s afely ainsi que la présence:

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

Le elem ordinaire ne suppose rien, donc il faut inspecter chaque élément de son argument de liste, ne peut pas gérer des listes infinies. ordElem peut. Ainsi donc,

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 est juste une liste de toutes les chances ci-dessus . Eh bien, nous savions que. Qu'en est-il de la prochaine étape?

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

Et l'autre,

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

C'est la séquence avec laquelle le tamis de Atkin travaille. Aucun multiple de 2, 3 ou sont présents dans celui-ci. Atkin et Bernstein travaillent modulo , à savoir qu'ils doublent la gamme:

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

Ensuite, ils utilisent des théorèmes sophistiqués pour connaître quelques propriétés de chacun de ces nombres et traiter chacun en conséquence. Le tout est répété (a-la la "roue") avec une période de .

• « Tous les numéros de n avec modulo soixante reste 1, 13, 17, 29, 37, 41, 49, ou 53 (...) sont premiers si et seulement si le nombre de solutions à 4x^2 + y^2 = n est impair et le nombre est squarefree. "

Qu'est-ce que cela signifie? Si nous savons que le nombre de solutions à cette équation est impair pour un tel nombre, alors il est premier si il est squarefree. Cela signifie qu'il n'a pas de facteurs répétés (comme 49, 121, etc).

Atkin et Bernstein utilisent pour réduire le nombre d'opérations d'ensemble: pour chaque prime (de et plus), nous énumérons (et la marque pour l'enlèvement) les multiples de sa place, donc ils sont beaucoup plus à part dans le tamis d'Ératosthène, il y en a moins dans une gamme donnée.

Le reste des règles sont:

• « Tous les numéros n modulo soixante reste 7, 19, 31 ou 43 (...) sont premiers si et seulement si le nombre de solutions à 3x^2 + y^2 = n est impair et le nombre est squarefree. "

• « Tous les numéros n modulo soixante reste 11, 23, 47 ou 59 (...) sont premiers si et seulement si le nombre de solutions à 3x^2 − y^2 = n est impair et le nombre est quadratfrei. »

Cela prend soin de tous les 16 numéros de base dans la définition de p60.

voir aussi: Which is the fastest algorithm to find prime numbers?

---

La complexité temporelle du tamis d'Eratosthène en produisant des nombres premiers jusqu'à N est O (N log log N), tandis que celle du tamis de Atkin est O (N) (en mettant de côté les optimisations supplémentaires log log N qui ne sont pas bien à l'échelle). La sagesse acceptée cependant est que les facteurs constants dans le tamis d'Atkin sont beaucoup plus élevés et donc il pourrait seulement payer haut au-dessus des nombres de 32 bits (N> 2), if at all.