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 »¹.

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:

Le symbole STEP n'est pas utilisé dans prime.c. En fait prime.h est commun aux diverses évolutions du programme que nous étudierons par la suite.
Il en est de même pour les déclarations des fonctions addlog, startinit et writelog.
Le tableau tab contient les nombres premiers. Il est initialisé manuellement jusqu'à son deuxième élément qui a pour valeur 3.
La variable n contient la valeur du nombre « candidat à la primalité » et index est l'indice du dernier nombre premier connu contenu dans tab. Si n est premier alors index sera incrémenté et n sera alors placé dans tab à l'emplacement pointé par la nouvelle valeur d'index. La variable isprime est initialisée à 1 (vrai). On considère en effet n premier jusqu'à preuve du contraire.
Le programme se présente comme une boucle infinie pour laquelle il n'y a que deux possibilités de sortie : soit, on a calculé le nombre de nombres premiers voulus, nombre défini par MAXTAB, soit on approche de UINT_MAX, entier non signé maximum représentable sous l'architecture considérée et défini dans le fichiers de déclaration limits.h fourni avec le compilateur. (La valeur de 203280218 pour MAXTAB correspond à UINT_MAX sur notre machine de référence).
Une clause de compilation conditionnelle, OUTPUT, permet d'activer ou non l'affichage des éléments de tab, i.e. les nombres premiers calculés. Il peut apparaître a priori bizarre de ne pas vouloir afficher les résultats d'un calcul. Néanmoins, ceci se révèle utile pour des essais de performances du moteur de calcul sans pollution par les ressources prises pour l'affichage du résultats. C'est notamment le cas si l'on cherche à étudier les influences des diverses options de compilation fournies par le compilateur.
On notera que le test définissant si un autre diviseur doit être essayé est exactement l'inverse de celui que nous avons envisagé formellement. On élève en effet au carré le diviseur essayé et on le compare au candidat. D'une part, ce petit subterfuge permet de s'affranchir des possibles erreurs d'arrondis qui seraient engendrées par l'appel à la fonction de la bibliothèque mathématique flottante de calcul des racines carrées. D'autre part, la multiplication de deux entiers et la comparaison du produit obtenu est plus rapide que l'appel à la racine carrée et la comparaison d'un entier avec un flottant. Il ne faut pas oublier que pour une valeur de MAXTAB égale à un million ce test sera exécuté 491022541 fois. Une micro-seconde de gagnée par test équivaut à plus de huit minutes sur le temps d'exécution du programme.
Le tableau tab est maintenu en mémoire. Pour une valeur de MAXTAB égale à cent millions et une taille d'entier de quatre octets, il occupera en mémoire quatre cents millions d'octets. Il faut donc prévoir en conséquence l'espace de pagination et les droits de s'en servir pour l'utilisateur au nom duquel ce programme sera lancé si l'on ne dispose pas de la mémoire physique qui va bien.
On notera que, paradoxalement, le programme n'engendre en lui-même que peu de pagination. Ceci est dû au fait que, plus on s'éloigne de l'origine du tableau tab, plus la probabilité d'aller plus loin est faible. Il ne pénalise donc pas lourdement les autres process (en tout cas beaucoup moins que le lancement d'une ou plusieurs sessions X sur un ordinateur faiblement pourvu en mémoire physique).

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 >

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