Définition

Est appelé "nombre premier", un nombre entier positif différent de 1 qui n'est divisible que par 1 et par lui-même (source Quid).

Quelques nombres premiers

Par exemple, voici la liste des nombres premiers inférieurs à 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

Pour obtenir cette liste, il suffit d’observer une table de multiplication de Pythagore, à partir de 2 jusqu'à 10. Tous les nombres qui n'apparaissent pas sont les nombres premiers (zone bleutée au milieu de la table).

Ci-dessous la représentation de la table de multiplication de Pythagore

 
(source Wikipédia)

Et dans notre tableur favoris…

Une formule serait-elle capable de calculer les valeurs des nombres premiers ?

Nous allons voir cela ci-dessous… 

Dans une feuille de calcul, si nous devions établir la table de multiplication de Pythagore, pour une version antérieure à Office 2007, nous ne pourrions aller au-delà de la valeur de 65536 (256*256). Ce qui ne représente que 6543 nombres premiers.

Nous allons voir comment concevoir, une formule capable de retourner 65536 nombres premiers.

1ère étape : La table des multiples

Nous n'allons pas créer pas la table de multiplication à l’identique.

Pour déterminer l’autre valeur de l’axe de notre table (en colonne), nous allons utiliser la valeur du dernier nombre, le 31. Nous savons que la liste va du plus petit au plus grand, le prochain nombre premier sera forcément supérieur à 31, et même supérieur à 32, les chiffres paires ayant comme diviseur le 2, ne sont donc pas nombres premiers. Dans notre formule Excel, nous pouvons sans provoquer d’erreur, additionner au dernier nombre 31, la valeur 2. Appelons ce nombre : «valeur de base». 

Cette valeur de base, sera notre point de départ pour déterminer les multiples. Le multiple sera la valeur immédiatement supérieure à la valeur de base dans la table de multiplication correspondante. Par exemple, dans la table de multiplication des 7 (7, 14, 21, 28, 35, 42, etc...), le 35 est le multiple immédiatement supérieur à 33, il sera donc retenu. Autre exemple : dans la table de multiplication des 13 (13, 26, 39, 52, etc...), ce sera la valeur 39.

 
Appelons cette table : «table des multiples»

Toutefois, en laissant la table sous cette forme, nous allons vite rencontrer un problème de taille. En effet, dans l’étape suivante, nous devrions trouver la plus petite valeur ne figurant pas dans la table des multiples. Or, dans cet exemple, la plus petite valeur supérieure à 31 et ne figurant pas dans les résultats serait le 36. Ce nombre est un multiple de 2 et de 3, ce n’est donc pas un nombre premier. Notre méthode est donc incomplète. Comment résoudre ce problème ?

Il faut pouvoir exclure les autres valeurs des multiples des nombres premiers qui suivent. Pour cela, nous allons rajouter dans l’axe des colonnes d’autres «valeurs de base», et par pas de deux.

Ce qui donne ceci :

On s’aperçoit alors que la valeur 36 est bien présente dans la table des multiples et ne devra donc pas être retenue.

Comment traduire en formule cette table de multiples ?

Pour calculer les valeurs des multiples supérieurs à la valeur de base, nous pourrions utiliser la formule suivante :

=(ENT(33/2)+1)*2

mais nous préférerons une fonction de base d’Excel qui se nomme PLAFOND.

=PLAFOND(valeur de base ; liste des nombres premiers)

2ème étape : La recherche

Pour déterminer la première valeur non présente dans la table des multiples, il faut définir une liste de valeurs. Appelons cette liste « liste d’inconnus ». Le premier élément de cette liste sera égale à la valeur de base et les suivants auront un pas d’incrément de n+1.

Dans Excel, les fonctions de la catégorie «recherche et matrice» fonctionnent sur une plage de recherche n’ayant qu’une seule colonne ou ligne. Ce n’est pas le cas pour notre table des multiples. Comment le résoudre ce problème de table multidimensionnelle ?

Nous allons utiliser FREQUENCE, cette fonction retournera pour chaque valeur de la liste d’inconnus, la quantité trouvée dans la table des multiples.

En reprenant la table des multiples en fin d’étape 1, FREQUENCE retournera un tableau contenant ceci :

En examinant ce tableau, on observe que la première quantité à 0 représente un nombre premier.

Maintenant, il faut savoir où se trouve la première quantité à 0 dans la table.

La fonction EQUIV répond exactement à cette demande.
 

Les deux fonctions imbriquées donnent ceci :

=EQUIV(0;FREQUENCE(table des multiples;table des inconnus);0)

En spécifiant la valeur 0 au troisième argument de la fonction EQUIV, nous nous assurons d'obtenir la valeur exacte et non la valeur la plus proche.

Pour finir il suffit d’additionner la position de la valeur à 0 dans le tableau à la valeur de base, pour obtenir la nouvelle valeur du nombre premier.

3ème étape : Calcul des valeurs incrémentées

Dans la table des multiples, on prend la valeur de base et on l’additionne à une valeur de 2, de 4, de 6, de 8, etc...

Dans Excel, la fonction LIGNE :  =LIGNE(A1) retourne 1, =LIGNE(A2) retourne 2, etc...

Pour obtenir un incrément de 2, il suffit de multiplier la valeur retournée par 2.

4ème étape : Les matrices

Nous n’allons pas créer dans les plages de cellules les différentes tables « multiples », « inconnus », « incrément1 » et « incrément2 » pour calculer chaque nombre premier, cela serait un travail fastidieux, voire impossible à faire. Comment faire alors ?

Nous allons passer par les matrices.

Une matrice est comme une plage de cellules, mais sans représentation physique des valeurs. Elle mémorise les résultats d’une partie de la formule, mais a un gros inconvénient : c’est sa durée de vie très limitée. En effet, une fois le résultat de la formule retournée, le contenu de la matrice n’est plus accessible aux autres formules de la feuille de calcul, ni à une autre partie de la formule. Dans notre cas, chaque formule va redéfinir les tables d’incrément qui ont scrupuleusement le même contenu. Une matrice est composée au minimum de deux valeurs et en général, elle est représentée sous forme verticale.

Comment alimenter les différentes matrice ?

Pour la suite des explications, les plages A1:A57 et B2:B115 ne contiennent aucune valeur et la plage C1:C11 contient les nombres premiers de 1 à 31.

Pour les matrices d’incréments :

=LIGNE(A1) ne retourne qu’une seule valeur. Pour que cette fonction retourne une matrice, il suffit de mettre dans la fonction une plage de cellules comme ceci =LIGNE(A1:A100). La matrice retournée au reste de la formule, aura ainsi 100 valeurs (de 1 à 100).

=31+(LIGNE(A1:A57)*2) retournera donc notre «matrice de valeurs de base»

Dans la 1ère partie, nous avons vu la fonction PLAFOND qui alimentait la table des multiples.

=PLAFOND(31+2;C2:C12) 

Sous cette forme, la matrice retournée est correcte. Mais comment intégrer dans cette matrice le problème soulevé en 1ère partie ?

=PLAFOND(31+(LIGNE(A1:A57)*2);C2:C12)

Cette codification n’est pas permise par Excel qui renvoie un message d’erreur #N/A.

Les fonctions ne pouvant pas combiner deux matrices verticales à l’exception des fonctions de produit matriciel (ce n’est pas le sujet ici). Par contre, elles sont capables de combiner une matrice verticale et une autre horizontale.

Comment passer d’une matrice verticale à une matrice horizontale ?

La fonction TRANSPOSE permet ce basculement.

Tout ceci se traduit donc par :

=PLAFOND(31+(LIGNE(A1:A57)*2);TRANSPOSE(C2:C12))

Cette formule retourne une matrice verticale et horizontale :

5ème étape : Concrètement sur la feuille de calcul

Nous avons maintenant toutes les bases pour écrire la formule.

Il faut un point de départ à notre formule car la fonction TRANSPOSE nécessite une référence ayant au minimum deux cellules. Mettons dans les cellules C1 la valeur 1, en C2 la valeur 2 et en C3 la valeur 3.

Puis, dans la cellule C4, on saisie la formule ci-dessous en la validant par les touches Ctrl+Shift+Entrée.

=C3+1+EQUIV(0;FREQUENCE(PLAFOND(C3+(2*LIGNE(A$1:A$57));TRANSPOSE(C$2:C3));C3+LIGNE(B$2:B$115));0)

Cette formule retournant la valeur 5.

Vous pouvez faire un glisser vers le bas, vous aurez la suite...

6ème étape : Optimisation

Vous vous êtes sans doute posé la question : pourquoi avoir défini les tables incrémentées (A$1:A$57, et B$2:B$115) d’une telle longueur ?

Au départ de la conception de cette formule, j’avais utilisé une longueur de 200 lignes. Mais après avoir fait calculer à la formule tous les nombres premiers sur toute la colonne, j'ai pu constater que l’écart maxi entre deux nombres premiers consécutifs était de 114, d’où la limitation de ces deux plages.

Peut-on encore optimiser la formule pour diminuer les temps de calcul ?

Dans la table de Pythagore de 10 par 10, il est possible de trouver les valeurs des nombres premiers dans la limite de 100. On peut donc appliquer le principe de la racine carré pour limiter la taille des matrices. 

Recherche de la position de la racine carrée du dernier nombre premier connu dans la plage des nombres premiers trouvés.

Ce qui se traduit par :

=EQUIV(RACINE(C3);C$1:C3;1))

Vous pouvez remarquer cette fois que pour le troisième argument de la fonction, la valeur est fixée à 1. Nous n’avons pas besoin de trouver la valeur exacte, mais la valeur la plus proche supérieure. Dans ce cas, il y a une obligation : la plage de recherche doit être triée. Ce qui est notre cas.

Connaissant cette position nous devons retourner la plage de cellules limitée, c’est la fonction DECALER qui le permettra :

=DECALER(C$2;;;EQUIV(RACINE(C3);C$1:C3;1)))

Voilà pour la plage raccourcie, cela paraît stupide, mais en diminuant la plage des nombres premiers, nous allons gagner un temps important. Si vous avez reporté la formule dans toute la colonne (de C4 à C65536), dans la dernière cellule C65536, la taille de la table des multiples n’est plus que de 907*57, comparée à 65534*57 de la formule de base.

Au final, pour les 65536 nombres, Excel aura calculé 401 552 631 multiples. Ce qui n’est rien, car sans limitation, Excel en aurait calculé 122 408 435 655.

La formule globale définitive devient donc :

=C3+1+EQUIV(0;FREQUENCE(PLAFOND(C3+(2*LIGNE(A$1:A$57));TRANSPOSE(DECALER(C$2;;;EQUIV(RACINE(C3);C$1:C3;1))));C3+LIGNE(B$2:B$115));0)

7ème étape : L’infini

Nous pouvons aller encore plus loin en collant la valeur du dernier nombre connu (cellule C65536) dans la cellule D1, puis en copiant la formule ci-dessous dans la cellule D2 (toujours à valider par Ctrl+Shift+Entrée) et en la tirant à nouveau vers le bas :

Oui, mais l’infini … ? 

Hélas, c'est impossible! Une fois obtenu le carré du dernier nombre premier de la colonne C, ce ne sera plus possible car la fonction PLAFOND ne peut calculer la table des valeurs de base avec une table des multiples multidimensionnelle. Enfin, cela porte tout de même à la valeur 675 031 489 609 (soit 821603*821603).

La version d’office 2007 portant à plus d'1 million le nombre de lignes d’une feuille de calcul…. C’est une autre histoire...

Remarquez au passage que tout ceci n’est rien, le dernier nombre premier calculé par les ordinateurs dépasse 20000 chiffres ! 

Y aurait-il une autre formule possible ? 

Oui en passant par le modulo, mais les calculs seront plus longs et la formule plus complexe...

 Auteur de cet article :  JeanMarie

Le fichier Excel :

Pour apprendre à utiliser cette formule et vous familiariser avec les matrices notamment, vous pouvez récupérer le classeur Exemple accompagnant cet article.

Le fichier Formule - Nombres premiers

Il y a 2 onglets dans ce classeur :