NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 29/04/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique      Brèves de Maths

      

NOMBRES PREMIERS

 

Débutants

Général

Propriétés

 

Glossaire

Nombres

premiers

 

 

INDEX

 

Nombres premiers

 

Débutant

Introduction

Barre magique

Sur Tableur

Les plus grands

Caractérisation

Un

 

Sommaire de cette page

>>> Principes du calcul

>>> Accès aux numéros de ligne

>>> Calcul en profondeur

>>> Bornes de calcul

>>> Adressage indirect

>>> Calcul des restes (modulo)

>>> Restes non nuls

>>> La formule magique

>>> Bilan

>>> Raffinement

 

 

 

 

 

 

 

NOMBRES PREMIERS

Recherche sur le tableur Excel

 

 

La recherche des nombres premiers sur tableur peut prendre plusieurs formes:

*    Énumérer tous les nombres entiers et les diviser par les nombres premiers successifs à la manière du crible d'Ératosthène. Excellent exercice d'apprentissage du tableur, mais non pertinent pour de grands nombres; ou alors

*    Trouver un moyen de tester directement si un nombre est premier ou non. Trouver la formule magique. Elle existe. Sa mise au point nécessite de bonnes explications.

Je vous propose d'arriver à établir cette formule pas à pas.

 

Le résultat de cette page mérite vraiment le détour, même s'il faut s'accrocher un peu pour aller jusqu'au bout. Cependant si vous voulez ignorer les explications, allez directement à la formule et mettez la dans votre tableur. Ça marche!

 

 

 

Approche – Les principes fondamentaux du calcul

 

*    Nous allons utiliser la méthode du crible d'Ératosthène, en très bestial.

*  On élimine le premier 2 pour ne tester que les premiers impairs.

*  Ultérieurement, on pourra limiter les recherches aux nombres de 1 à racine de N).

 


Le nombre N à tester est divisé par tous les nombres k de 3 à N-1.

Si une seule division donne un reste nul, le nombre est divisible; il est composé; il n'est pas premier.

Autre formulation:

Si aucune division ne donne un reste nul, alors, N est un nombre premier.

 

 

*    Nous allons nous intéresser aux restes de la division. Ou, plus exactement, aux congruences.
Si N est congruent à 0 pour toutes les valeurs, il est premier.

 

Si N mod (k)  0

pour tous les k = {de 1 à N-1},

alors N est premier.

*    Pour balayer tous les nombres de 1 à N-1, nous allons utiliser les numéros des lignes du tableur

 

"LIGNES" et "INDIRECT" sont des commandes Excel qui vont nous permettre d'accéder aux numéros des lignes.

 

*    Pour compacter tout ce calcul en une cellule seulement, nous allons faire des calculs cachés (sans se répandre sur les lignes et les colonnes du tableur, mais en profondeur cachée).

 

Le tableur Excel recèle la faculté de travailler en interne sur des tableaux (matrices) et d'en "sortir" le résultat dans une seule cellule.

 

 

 

Accès aux numéros de ligne

 

*    La commande LIGNE permet d'accéder au numéro de la ligne.

 

Note: Le contenu de A5 n'a aucune influence.

 

*    Autre exemple permettant de comprendre le fonctionnement et la suite.


 

 

 

 

Calcul en profondeur

 

*    Nous savons faire la somme classique des valeurs dans les cellules spécifiée avec la commande SOMME.

*    Associée à la Commande LIGNE, nous allons faire une somme en profondeur. Sur des nombres que nous ne voyons pas à l'affichage. La commande SOMME(LIGNE …)) va sommer les numéros des lignes des cellules spécifiées.

*  en spécifiant A1:A4, nous demandons la somme de 1 à 4 = 10

*  nous aurions pu indiquer B1:B4, nous aurions la même somme des numéros de lignes de 1 à 4 quelles que soient les colonnes. Avec A1:K4, même résultat!

*    Une seule condition importante: le tableur doit savoir que nous voulons ce calcul en profondeur. Pour cela: cliquer la fenêtre d'édition et faire en même temps Contrôle-Majuscule-Entée. Deux accolades apparaissent dans la fenêtre pour signifier la prise en compte. Refaire cette opération chaque fois que vous entrez ou modifiez une formule.
 

 

*    Nous savons faire un calcul (ici la somme, mais on aurait pu mettre autre chose) qui balaye tous les nombres de n à m. 

 

 

Bornes de calcul

 

*    Nous devons pouvoir spécifier les bornes de calcul. Pour la recherche de la primalité, il s'agit de n = 2 et  m = N-1. Comment si prendre?

*    Les deux bornes doivent se suivre, séparées par deux points: 2:10, par exemple.

*    Nous allons écrire le 2: en le mettant entre guillemets et lui associer le 10. L'association (concaténation) se fait avec le symbole &; Quant à la valeur 10, que nous voulons spécifier à notre guise, nous la plaçons en A1 (par exemple) et nous appelons A1 dans notre commande.

 

Note: si nous demandons SOMME(2:10), nous aurons le calcul de la somme de tous les nombres qui se trouve sur les lignes de 2 à 10, quelles que soient les colonnes, à condition de faire CRTL-MAJ-ENT.

 

Voir Esperluette

 

 

Adressage à rebond dit INDIRECT

 

*    Comment faire la somme des nombre de 2 à 10 (bornes de l'exemple précédent)? Sachant que nous voulons la valeur dans une cellule à chaque fois que nous modifions la borne supérieure (ici 10).

*    Imaginez que l'on vous dise d'aller chercher la clé du coffre. Oui, mais l'endroit est indiqué sur un billet placé dans le tiroir du bureau. Vous avez là un accès après un "rebond" qui est appelé adressage indirect en informatique.

*    La commande INDIRECT va nous permettre cet adressage indirect: la commande 2:10 devient 2:A1 et nous plaçons 10 en A1.

 

 

*    Sachant faire la somme de 2 à un nombre spécifié (ici 10, par exemple), nous pouvons faire d'autres opérations sur cette étendue.

*    Par exemple, et nous revenons à nos moutons, la commande suivante va désigner les numéros des lignes depuis la ligne 2 à  la ligne définie en A1.

LIGNE(INDIRECT("2:"&A1))

 

 

 

 

 

Il ne demande que son reste!

 

*    Les familiers de ce site connaissent la division, les restes de la division et cette opération qui consiste à ne s'intéresser qu'aux restes en se fichant du quotient. C'est le calcul modulo (ou des congruences).

*    Au lieu de calculer la somme nous allons calculer la congruence du nombre N selon tous les nombres de 2 à 10. Exemples avec N  = 11 puis N  = 12.

*    D'abord, voyons comment ça fonctionne toutes voiles déployées.
 

 

*    En colonne B, toutes les divisions par les nombres plus petits que 11 donnent un reste non nul. 11 est un nombre premier

*    En colonne C, pour le nombre 12, un reste nul est témoin de divisibilité. La présence d'un seul 0 est signe que le nombre est composé.

*    L'écriture de notre commande:

MOD (nombre,                   diviseur)

MOD (A1 où se trouve N, les nombres k de 2 à N-1, les uns après les autres)

MOD(A1;LIGNE(INDIRECT("2:"&A1-1)))

 

 

 

 

 

Tous les restes non nuls

 

*    Nous devons nous assurer que tous les restes de la division de n par les nombres de 2 à N-1 sont non-nuls.

Le reste 1 et le reste 2 et … et le reste N-1  sont différents de 0.

En langage plus proche du tableur:

ET(reste1; reste2; … reste N-1) <> 0
 

*    Si c'est vrai, le nombre est premier, sinon il est composé:

 

Si ( ET ( (reste1; reste2; … reste N-1) <> 0); "premier"; composé" )

Entre guillemets pour indiquer de mettre ce texte dans la cellule.

 

 

 

 

La formule magique

 

*    Nous sommes au bout en introduisant dans cette dernière formule l'expression des restes vue plus haut

 

 

=SI(

 

 

;

"premier";"composé")

 

ET(

 

)

 

 

 

 

(MOD

 

 

 <>0)

 

 

 

 

 

 

(A1;

 

)

 

 

 

 

 

 

 

LIGNE(

 

)

 

 

 

 

 

 

 

 

 

INDIRECT("2:"&A1-1)

 

 

 

 

 

=SI(ET((MOD(A1;LIGNE(INDIRECT("2:"&A1-1)))<>0));"premier";"composé")

 

*    Voici le résultat.

Bien indiquer le nom de la cellule où se trouve N. Ci-dessus en A1; dans l'exemple ci-dessous en A3. Les cellules B1 et B2 pour N = 1 et N = 2 ne sont pas calculées car triviales.

 

 

 

Bilan

Vous pouvez copier et coller la formule ci-dessus en B1.

N'oubliez pas de cliquer la fenêtre d'édition (là où se trouve fx) et de faire CRTL-MAJ-ENT. Les accolades apparaissent? Oui! C'est bon!

Tapez un nombre en A1. vous avez la réponse immédiatement.

Vous pouvez tirer les cellules vers le bas obtenir la primalité des nombres suivants.

Vous pourrez tester la primalité de N jusqu'à 228 – 1 = 268 435 455.

Voir Puissances de 2

 

 

 

 

Raffinement

 

*    Au lieu de tester tous les nombres de 2 à N-1, on peut limiter l'exploration à racine de N, ou du moins au nombre entier juste supérieur. On utilise la commande arrondi supérieur en précisant que nous voulons 0 chiffres après la virgule.

*    La commande devient:



 

=SI(ET((MOD(A1;LIGNE(INDIRECT("2:"&ARRONDI.SUP(RACINE(A1);0))))<>0));"Premier";"")

 

ATTENTION!

Pour activer la formule ne pas oublier de

*       cliquer la formule dans la zone formule;

*       faire Ctrl –Majuscule – Entrée, les trois appuyées en même temps;

*       la formule est entourée par des accolades {  } => c'est BON.

 

 

 

 

 

 

Voir

*    Nombres magiques – Index

*    Séquence en six

*    Nombres premiers jumeaux - Caractérisation

*    Nombres premiers jumeaux - Développements

Aussi

*    Les nombres premiers – Introduction et développements

Site

*    Testing Prime Numbers in Excel – Charles H. Pearson (où vous trouverez, en anglais, de nombreuses autres explications)

Cette page

http://villemin.gerard.free.fr/aMaths/Premier/Tableur.htm