CVNI

A, B, ... Canard !

Nombres premiers

Méthode de calcul

Recherche exhaustive

Le crible d'Erathostène

Une des méthodes les plus simples est le principe dit « crible d'Erathostène »1.

Formellement, l'idée sous jacente peut être exprimée de la manière suivante:

Intuitivement, cela revient à dire que tout entier naturel composé possède au moins un diviseur différent de 1 et inférieur ou égal à sa racine carré. Dès lors, soit un entier naturel n donné, il suffit d'essayer de le diviser par les entiers naturels non nuls différents de 1 et inférieurs ou égaux à sa racine carrée. Si l'on ne trouve aucun diviseur, alors n est premier.

Il serait inutile, en effet, de continuer. En supposant que l'on trouve un diviseur q qui serait strictement supérieur à , alors il en existerait un autre p qui lui serait strictement inférieur et que, par conséquent, l'on aurait déjà trouvé.

Cette idée a des implications très intéressantes. Savoir si un entier n est premier ne requiert qu'au plus essais de divisions.

De plus, si l'on suppose déjà connus les nombres premiers inférieurs ou égaux à , il suffira de rechercher les diviseurs dans ce sous-ensemble, ce qui réduira encore d'avantage le nombre d'itérations nécessaires.

Ce sont ces considérations qui sont mises en oeuvre dans la série des programmes prime.

Un premier programme: prime.c

Le premier programme que nous allons examiner permet un calcul exhaustif des nombres premiers représentables sous forme d'entiers non signés dans le format natif géré par le compilateur. Voici le source de ce programme simpliste.

#include "prime.h"

#include <limits.h>
#include <stdio.h>

unsigned long tab[MAXTAB];


void main(void)

{       unsigned long i,n,index;
        int isprime;

        printf("Calcul des %lu premiers nombres premiers.\n\n", MAXTAB);

        tab[0]=2L;
        tab[1]=3L;
        index=1;
        n=3;

        for (;;)
        {       n += 2;
                if (n>=UINT_MAX-3) break;
                i=0;
                isprime=1;

                do
                {       i++;
                        isprime = n%tab[i];
                }
                while (isprime && tab[i]*tab[i]<=tab[index]);


                if (isprime)
                        tab[++index]=n;
        
                if (index == MAXTAB-1L) break;
        }

#ifdef OUTPUT
                for (i=0; i<=index; i++)
                        printf("%lu\n", tab[i]);
#endif

        exit(0);
}



Ce programme appelle un fichier d'en-tête prime.h que voici

#define STEP 1000000L
#define MAXTAB 203280218L
//#define MAXTAB     182000000L
//#define MAXTAB    20000001L
//#define MAXTAB 1000000L

extern void addlog(unsigned long, unsigned long *);
extern unsigned long startinit(unsigned long *);
extern void writelog(char *, unsigned long , unsigned long *);



Quelques commentaires:

La compilation doit générer quelque chose approchant ceci :

ns@delta:~/crypto/prime > time make prime
gcc -O3 -Wall -m486 -fomit-frame-pointer -fforce-addr -fforce-mem -malign-loops=2 -malign-functions=2 -malign-jumps=2 -funroll-all-loops -ffast-math -DOUTPUT  -c -o prime.o prime.c
prime.c:11: warning: return type of `main' is not `int'
gcc -O3 -Wall -m486 -fomit-frame-pointer -fforce-addr -fforce-mem -malign-loops=2 -malign-functions=2 -malign-jumps=2 -funroll-all-loops -ffast-math prime.o -o prime
strip prime

real    0m2.835s
user    0m2.290s
sys     0m0.370s
ns@delta:~/crypto/prime > ls -l prime
-rwxr-xr-x   1 ns       users        3480 Jul  1 01:36 prime
ns@delta:~/crypto/prime > 



Si vous voulez vérifier le résultat de la compilation, voici pour une valeur de MAXTAB égale à un million le résultat

ns@delta:~/crypto/prime > time prime > prime.output

real    15m17.933s
user    5m21.830s
sys     0m3.450s
You have mail in /var/spool/mail/ns
ns@delta:~/crypto/prime > head prime.output
Calcul des 1000000 premiers nombres premiers.

2
3
5
7
11
13
17
19
ns@delta:~/crypto/prime > tail prime.output
15485761
15485773
15485783
15485801
15485807
15485837
15485843
15485849
15485857
15485863
ns@delta:~/crypto/prime >




logo alapage


1Ce mathématicien grec est aussi connu pour avoir calculé avec les moyens de l'époque la circonférence terrestre.