Question

Je suis en train de réaliser un projet et j’ai besoin d’une méthode efficace pour calculer les nombres premiers. J'ai utilisé le tamis d'Eratosthenes mais j'ai constaté que le Le tamis d'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? Un exemple de code (de préférence en C ou en python) serait brillant.

Éditer: merci de votre aide, la seule chose que je ne comprends toujours pas, c’est ce à quoi les variables x et y font référence dans le pseudo-code. Quelqu'un pourrait-il m'éclairer un peu, s'il vous plaît?

Était-ce utile?

La solution

La page de wiki est toujours un bon point de départ car elle explique l'algorithme en complet et fournit un pseudocode commenté. (NB: il y a beaucoup de détails, et comme le site Web du wiki est fiable, je ne le citerai pas ici.)

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

L’espoir que cela aide.

Autres conseils

Un article de Wikipedia a une explication:

  • "L'algorithme ignore complètement les nombres divisibles par deux, trois ou cinq. Tous les nombres avec un reste même modulo-soixante sont divisibles par deux et non premiers. Tous les nombres avec un reste modulo-soixante divisible par trois sont également divisibles par trois et non premiers. Tous les nombres avec un reste modulo-soixante divisible par cinq sont divisibles par cinq et non 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 cela se passe pendant quelques premières étapes: 

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 . IOW, il ne contiendra que des nombres coprimes avec 2 & # 8212; Aucun nombre dans p2 n’a comme facteur 2 . Pour trouver p2 , nous n'avons pas besoin de tester la division par 2 de chaque nombre dans [3 ..] (c'est-à-dire 3 et plus, 3,4,5,6,7, ... ), car 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 est semblable à elem (c.-à-d. test de is-element ), il suppose simplement que son argument de liste est un ordre, liste croissante de numéros, de sorte qu'il puisse 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 n'assume rien, vous devez donc inspecter chaque élément de son argument de liste, vous ne pouvez donc pas gérer de listes infinies. ordElem peut. Alors, alors, 

p2 = [y | y <- [3..], not (ordElem y [2,4..])]  -- abstract this as a function, diff a b =
   = diff      [3..]                 [2,4..]    --       = [y | y <- a, not (ordElem y b)]
   -- 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 simplement une liste de toutes les cotes supérieures à 2 . Eh bien, nous le savions cela . 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 la suivante, 

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 dans laquelle fonctionne le tamis d’Atkin. 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 plage: 

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 certaines propriétés de chacun de ces nombres et les traiter en conséquence. Le tout est répété (à la "roue") avec une période de 60 .

  • "Tous les nombres n avec modulo-soixante restants 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 cela signifie? Si nous savons que le nombre de solutions à cette équation est impair pour un tel nombre, il est alors premier si il est carré. Cela signifie qu'il n'y a pas de facteurs répétés (comme 49, 121, , etc.).

Atkin et Bernstein l’utilisent pour réduire le nombre total d’opérations: pour chaque nombre premier (à partir de 7 ), nous énumérons (et marquons pour suppression) les multiples de son carré , ils sont donc beaucoup plus éloignés les uns des autres que dans le tamis d’Ératosthène; ils sont donc moins nombreux dans une plage donnée.

Les autres règles sont les suivantes:

  • "Tous les nombres n avec modulo-soixante autres 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 nombres n avec modulo-soixante restants 11, 23, 47 ou 59 (...) sont premiers si et seulement si le nombre de solutions à 3x ^ 2 & # 8722; y ^ 2 = n est impair et le nombre est carré. "

Ceci s’occupe des 16 numéros principaux de la définition de p60 .

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

La complexité temporelle du tamis d’Ératosthène dans la production de nombres premiers jusqu’à N est O (N log log N) , tandis que celle du tamis d’Atkin est O (N) (en mettant de côté les optimisations supplémentaires log log N qui ne sont pas bien dimensionnées) La sagesse admise est que les facteurs constants dans le tamis d’Atkin sont beaucoup plus élevés et que cela pourrait ne rapporter que très au-dessus des nombres 32 bits ( N> 2 32 ) , le cas échéant .

  

Éditer: la seule chose que je ne comprends toujours pas, c’est ce à quoi les variables x et y font référence dans le pseudo-code. Quelqu'un pourrait-il m'éclairer un peu, s'il vous plaît?

Pour une explication de base de l'utilisation courante des variables "x" et "y" dans le pseudo-code de page Wikipedia (ou d'autres applications plus performantes du tamis d'Atkin), vous pouvez trouver mon réponse à une autre question connexe utile.

Voici une implémentation c ++ du tamis d’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;
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top