Recherche nombres premiers sur tableur

É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 f_x) 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'à 2²⁸ – 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://diconombre.fr/aMaths/Premier/Tableur.htm