Nombres premiers - eratosthene quasi illimité


Commenter

Contenu du snippet

Ce petit programme (80 lignes) affiche tous les nombres premiers.
Paramètre : combien vous en voulez (100 par défaut).
Il est basé sur le fameux crible d'Eratosthène, mais contrairement à l'habitude on ne parcourt le tableau qu'une fois, en
'cochant' les non-premiers au fur et à mesure. Attention, pas de test d'erreur dans ce code !
Le programme est très simple, l'algo aussi (si, si!), mais vous aurez peut-être quand même du mal à suivre ...

A l'origine je voulais le soumettre, après 'amélioration', à un concours ObfuscatedC, mais je n'ai pas le temps !

ps. J'ai fait le même en Piet, pour les amateurs ...

Source / Exemple : 


/* **************************************************** */
/*                     Erat.C                           */
/* **************************************************** */
/* Affichage des N premiers premiers                    */
/* **************************************************** */
/* (c) BZRD - 2006                                      */
/* **************************************************** */

#include "stdio.h"
#include "stdlib.h"
#include "memory.h"

unsigned long *P;

/*
// Pour afficher le contenu du buffer, éventuellement (ce qui explique que P soit en globale)
void dumpPile(char *msg, int n)
{
   int   i;

   printf("%s -- ", msg);
   n = 2*n + 4;
   for (i=n-1; i>=0; i--)
      printf("%d ", P[i]);
   printf("\n");
}


  • /


void main(int argc, char **argv)
{
   unsigned long   n = 2;
   unsigned long   a,b,c;
   unsigned long   k, i;
   unsigned long MAXPILE = 100;

   if (argc > 1)
      MAXPILE = atoi(argv[1]);

   P = (unsigned long *)malloc(2*MAXPILE*sizeof(unsigned long));

   // Il faut au moins avoir les valeurs 3 et 5 -- premiers premiers impairs
   P[0] = 3; P[1] = 9; 
   P[2] = 5; P[3] = 10;
   P[4] = 7; P[5] = 14;

   printf("Liste des %d premiers nombres premiers\n 2 - 3 - 5 - 7 ", MAXPILE);
   
   MAXPILE -= 2;

   while (n < MAXPILE)
   {
      c = P[0];
      b = P[1];
      a = b+c;

      if (a >= P[3])
      {
         for (k=1; k<=n; k++)
         {
            P[2*(k-1)]   = P[2*k];
            P[2*(k-1)+1] = P[2*k+1];
            if (a <= P[2*(k+1) + 1])
            {
               P[2*k] = c;
               P[2*k+1] = a;
               break;
            }
         }
      }
      i = (b+1) | 1;

      b = P[1];
      c = P[2*n+1];
      
      for (; i<b; i+=2)
      {
         if (i!=c)
         {
            n++;
            P[2*n]   = i;
            P[2*n+1] = 2*i;
            printf("- %d ", i);
         }
      }
   }
}

Conclusion :


Si ça interesse quelqu'un j'essaierai de commenter.

Limitation à 2^31 pour les nombres affichés, mais ça dépend de toute façon de votre mémoire : pour afficher les N premiers nombres,
j'alloue un tableau de 2N longs.
Et puis, pour exploser mémoire et capacité de calcul, il vous faudra quand même être patient !

Affichage avec Erat 100 :
2 - 3 - 5 - 7 - 11 - 13 - 17 - 19 - 23 - 29 - 31 - 37 - 41 - 43 - 47 - 53 - 59 - 61 - 67 - 71 - 73 - 79 - 83 - 89 -
97 - 101 - 103 - 107 - 109 - 113 - 127 - 131 - 137 - 139 - 149 - 151 - 157 - 163 - 167 - 173 - 179 - 181 - 191 -
193 - 197 - 199 - 211 - 223 - 227 - 229 - 233 - 239 - 241 - 251 - 257 - 263 - 269 - 271 - 277 - 281 - 283 - 293 -
307 - 311 - 313 - 317 - 331 - 337 - 347 - 349 - 353 - 359 - 367 - 373 - 379 - 383 - 389 - 397 - 401 - 409 - 419 -
421 - 431 - 433 - 439 - 443 - 449 - 457 - 461 - 463 - 467 - 479 - 487 - 491 - 499 - 503 - 509 - 521 - 523 - 541

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (bzrd)