RECHERCHE DE NOMBRES PREMIERS PAR LE CRIBLE D'ERATOSTHENE

/*
 *  PREMIER.C - Affiche tous les nombres premiers de 0 à n sur la
 *  sortie standard, par le crible d'Eratosthène.
 *  Testé sur un Pentium 4, l'obtention de la liste de tout les nombres
 *  premiers de 0 à 1 000 000 000 (552 807 324 octets) né‚cessite 1mn 18s.
 *
 *  Développé par Michel Blancard.
 *  Version 2.2
 *  Dernière modification le 06/07/2006.
 */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <conio.h>

void main(int argc, char **argv)
{
  unsigned char *tableau;
  unsigned long i, j;
  unsigned long taille;
  unsigned long nbr_max;

  if(argc < 2)
  {
    cprintf("Syntaxe incorrecte.\n\r");
    cprintf("Syntaxe correcte : \"premier nbr_max [> *.*]\".\n\r");
    cprintf("nbr_max - maximum pour la recherche");
    return;
  }
  if((argv[1][0] < '0')&&(argv[1][0] > '9'))
  {
    cprintf("Syntaxe incorrecte.\n\r");
    cprintf("Syntaxe correcte : \"premier nbr_max [> *.*]\".\n\r");
    cprintf("nbr_max - maximum pour la recherche\n\r");
    return;
  }

  nbr_max = atol(argv[1]) + 1;
  taille = (nbr_max + 14) >> 4;    // On ne stocke que les nombres impaires.
  if((tableau = malloc(taille)) == NULL)
  {
    cprintf("Memoire disponible insuffisante.\n\r");
    return;
  }

  for(i=1; i<taille; i++)
  {
    tableau[i] = 255;          // Initialise les bits … 1 sauf le premier
  }                            // (nombre 1 non premier de toute fa‡on)
  tableau[0]=254;              // 252 <=> 11111110

  /*
   * Raye tout les nombres non premiers (environ 40 % du temps d'execution).
   */
  for(i = 1; i <= (unsigned long)sqrt((double)nbr_max) / 2; i++)
  {
    if(tableau[i >> 3] & (unsigned char)(1 << (i & 7)))
			       // si c'est un nombre premier
    {                          // alors on ‚limine tout ses multiples
      for(j = (4 * i * i) + (4 * i) + 1; j < nbr_max; j += (i * 4) + 2)
      {
        tableau[j >> 4] = tableau[j >> 4] & (unsigned char)(~(unsigned char)(1 << (((j - 1) / 2) & 7)));
      }
    }
  }

  /*
   * Affiche les nombres premiers (environ 60 % du temps d'execution).
   */
  if(nbr_max > 2)
  {
    printf("2\n");    // le nombre 2 n'est pas dans la liste
  }
  for(i=1; i<nbr_max / 2; i++)
  {
    if((tableau[i >> 3] & (unsigned char)(1 << (i & 7))) > 0)
    {
      printf("%lu\n", (i * 2) + 1);
    }
  }

  free(tableau);
}