Tutoriels > Tutoriels & Astuces Excel > Fonctions & Formules > Formule pour Nombres Premiers

Formule pour Nombres Premiers

Publié par JeanMarie le 29-08-2007 (12173 lectures)

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

 La Table 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… 



Il suffit de mettre en pratique ce qui est écrit ci-dessus : création de la table et recherche de valeurs ne figurant pas dans la liste.

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.

 

Partant du principe que nous connaissons déjà les nombres premiers allant de 2 à 31, pour créer notre table, on va s’appuyer sur ces nombres premiers connus. Dans notre table, ces nombres seront les valeurs d’entête de ligne.

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.

 Table des multiples
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 :



Table des multiples corrigée

 

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 :

Tableau FREQUENCE

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)

Attention! 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 :

 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 :

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

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.

Formule - Nombres premiers Le fichier Formule - Nombres premiers

 

Il y a 2 onglets dans ce classeur :

  • Le premier explique brièvement comment utiliser la formule génératrice de nombres premiers
  • Le deuxième décortique le fonctionnement de cette formule et vous permet de visualiser le détail du calcul aux fins pédagogiques. Vous aurez ainsi la possibilité de visualiser pour les valeurs de base de 5 à 283, le contenu des différentes tables. Pour cela, il suffit simplement de choisir une valeur de base dans la liste déroulante en cellule G7.

Pour toutes vos questions ou si vous rencontrez des difficultés, n'hésitez pas à rejoindre nos Forums de Discussions !

 

Autres articles dans cette catégorie Publié le Vues
Rechercher une Fonction 28-05-2013 3119
T() - Tester et renvoyer du texte 02-07-2012 10610
EPURAGE() - Supprimer certains caractères indésirables 02-06-2012 23264
REMPLACER() - Echanger une chaîne de caractères par une autre 02-06-2012 10020
CTXT() - Convertir un nombre en texte 23-05-2012 34542
REPT() - Répéter des caractères un certain nombre de fois 26-04-2012 10082
L'Assistant Somme Conditionnelle 01-11-2011 7698
CELLULE() - Nom de l'onglet, du fichier ou du répertoire dans une cellule 03-10-2010 27465
EXACT() - Comparer deux chaînes de texte 26-04-2010 44137
Purgez les espaces inutiles ! 05-04-2010 62532
SUPPRESPACE() - Supprimer les espaces inutiles dans une cellule 05-04-2010 30862
STXT() - Extraire une chaîne de caractères au sein d'une autre 13-03-2010 73040
CHERCHE() TROUVE() - Retourne la position d'une chaîne de caractères 04-01-2010 67401
NBCAR() - Compter les caractères d'une chaîne de texte ou d'une plage de cellules 21-11-2009 17670
SUBSTITUE() - Remplacer une chaîne de texte par une autre 08-11-2009 73450
CAR() - CODE() : Utilisation des codes caractères 25-10-2009 18041
CONCATENER() - Assembler plusieurs chaînes de texte en une seule. 10-10-2009 18539
TEXTE() - Convertir une valeur numérique en texte formaté 29-09-2009 55067
DROITE() - GAUCHE() : Extraire les premiers ou derniers caractères d'une chaîne. 12-09-2009 88112
MAJUSCULE() - MINUSCULE() - NOMPROPRE(): Modifier la casse d'un texte 23-08-2009 6425
CNUM() - Convertir une chaîne en valeur numérique 19-08-2009 30643
DATEDIF() : Calculer la différence entre deux dates 26-07-2009 61008
Nommer une Plage Dynamique 06-12-2008 43473
Nommer une Plage de Cellules 05-12-2008 57587
Références Relatives & Absolues 05-12-2008 13267
Formule pour Nombres Premiers 29-08-2007 12174