Tamis d'Atkine explication

article de Wikipedia a une explication:

• "L'algorithme ignore complètement tous les nombres divisibles par deux, trois ou cinq. Tous les nombres avec un reste de modulo-soixante Pair sont divisibles par deux et non Premier. Tous les nombres avec le reste modulo-soixante divisible par trois sont aussi divisibles par trois et pas premier. Tous les nombres avec le reste modulo-soixante divisibles par cinq sont divisibles par cinq et non pas premiers. Tous ces restes sont ignorés."

commençons par le 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 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 ne doit contenir aucun multiple de 2 . Maintenant il ne contiendra que des nombres avec 2 - aucun numéro dans p2 a 2 comme facteur. Trouver p2 nous n'avons pas réellement besoin de tester divide par 2 chaque nombre dans [3..] (c'est-à-dire 3 et plus, 3,4,5,6,7,... ), parce que nous pouvons énumérer tous les multiples de 2 à l'avance:

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

ordElem , c'est comme elem (c'est à dire est-élément ), c'est juste assume que son argument de liste est une liste ordonnée, croissante de nombres, de sorte qu'il peut détecter la non-présence en toute sécurité ainsi que la présence:

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

L'ordinaire elem ne présumez de rien, il faut inspecter chaque élément de sa liste d'argument, donc ne peut pas gérer l'infini listes. ordElem le pouvez. Alors,

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 tous les cotes ci-dessus 2 . Eh bien, nous savions que . 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 le suivant,

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 D'Atkin fonctionne. Aucun multiple de 2, 3 ou 5 n'y est présent. Atkin et Bernstein travaillent modulo 60 , c'est-à-dire 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 certains théorèmes sophistiqués pour connaître certains les propriétés de chacun de ces nombres et traitent chacun en conséquence. Le tout est répété (la "roue") avec une période de 60 .

• "tous les nombres n avec le reste modulo-soixante 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 carré."

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

Atkin et Bernstein utilisent ceci pour réduire le nombre d'opérations globales: pour chaque prime (de 7 et plus), nous énumérons (et marquons pour enlever) les multiples de son carré , ainsi ils sont beaucoup plus éloignés que dans le tamis des Eratosthènes, il y a donc moins d'entre eux dans une gamme donnée.

les autres règles sont:

• "tous les nombres n avec modulo-soixante restants 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 carré."

• "tous les numéros 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 carré."

il s'agit de l'ensemble des 16 numéros de base figurant dans la définition de p60 .

Voir aussi: Quel est l'algorithme le plus rapide pour trouver des nombres premiers?

---

Le temps la complexité du tamis des Ératosthènes dans la production des nombres premiers jusqu'à N est O(N log n) , tandis que celle du tamis D'Atkin est O(N) (mettant de côté les optimisations supplémentaires log log N qui ne se dimensionnent pas bien). 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 ³² ) , si à tous les .

Edit: la seule chose que je ne comprends toujours pas est à quoi les variables x et y se réfèrent dans le pseudo code. Quelqu'un pourrait s'il vous plaît faire la lumière sur ce pour moi?

pour une explication de base de l'utilisation courante des variables 'x' et 'y' dans le pseudo-code de la page Wikipédia (ou d'autres implémentations meilleures du tamis D'Atkin), vous pourriez trouver ma réponse à une autre question liée utile.

Voici une implémentation c++ de sieve of atkins qui pourrait 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;
 }

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