Comment déterminer un nombre premier. Comment trouver des nombres premiers

Problème 2.30
Étant donné un tableau unidimensionnel A, composé de nombres naturels. Affiche le nombre de nombres premiers dans le tableau.

Tout d’abord, permettez-moi de vous rappeler ce que sont les nombres premiers.

Passons maintenant à la tâche. Essentiellement, nous avons besoin d’un programme qui détermine les nombres premiers. Et trier les éléments et vérifier leurs valeurs est une question de technologie. En même temps, nous pouvons non seulement compter, mais aussi afficher les nombres premiers du tableau.

Comment déterminer un nombre premier en Pascal

Je fournirai un algorithme de solution avec une analyse détaillée en Pascal. Vous pouvez voir la solution dans l’exemple de programme en C++.

IMPORTANT!
C’est là que beaucoup de gens peuvent se tromper. La définition dit qu'un nombre premier a lisse deux différents diviseur Par conséquent, le nombre 1 n’est pas premier (il n’est pas premier non plus, puisque zéro peut être divisé par n’importe quel nombre).

Nous vérifierons si un nombre est premier à l'aide de , que nous créerons nous-mêmes. Cette fonction retournera VRAI si le nombre est premier.

Dans la fonction, nous allons d'abord vérifier si le nombre est inférieur à deux. Si tel est le cas, ce n’est plus un nombre premier. Si le nombre est 2 ou 3, alors il est clairement premier et aucune vérification supplémentaire n'est requise.

Mais si le nombre N est supérieur à trois, alors dans ce cas, nous passerons en revue tous les diviseurs possibles, en commençant par 2 jusqu'à (N-1). Si le nombre N est divisible par un diviseur sans reste, alors ce n'est pas non plus un nombre premier. Dans ce cas, on interrompt la boucle (car cela ne sert à rien de vérifier davantage), et la fonction renvoie FALSE.

Cela ne sert à rien de vérifier si un nombre est divisible par lui-même (c'est pourquoi la boucle ne dure que jusqu'à N-1).

Je ne présenterai pas la fonction elle-même ici - regardez-la dans les exemples de programmes.

Résolution du problème 2.30 en Pascal ma tâche; //************************************************ **************** //CONSTANTES //****************************** ********* ********************************** COMPTE = 100 ; //Nombre d'éléments dans le tableau //**************************************** *********** ******************** // FONCTIONS ET PROCÉDURES //************ *********** ************************************** ** //****** ***************************************** * ******** // Vérifie si le nombre est premier // INPUT : N - nombre // SORTIE : TRUE - le nombre N est premier, FALSE - non premier //********** **************************************** **** IsPrimeNumber (N : MOT) : ; var je: ; commencer := VRAI ; N de 0..3 : début N Sortie ; fin; fin; i:= 2 à (N-1) faire si (N i) = 0 alors //Ce n'est pas un nombre premier commencer Résultat := FALSE; ; fin; fin; je : MOT ; X : MOT = 0 ; A : de MOT ; //************************************************ **************** // PROGRAMME PRINCIPAL //****************************** ********************************** start //Remplissez le tableau avec des nombres pour i:= 1 à COUNT faire A[i] := i; //Comptez et sélectionnez les nombres premiers dans le tableau pour i:= 1 jusqu'à COUNT do if IsPrimeNumber(A[i]) then start (X); Écrire(A[i], " ); fin; (#10#13"Nombre de nombres premiers = ", X); WriteLn("La fin. Appuyez sur ENTER..."); ; fin.

Solution au problème 2.30 en C++#inclure #inclure en utilisant l'espace de noms std ; //************************************************ **************** //CONSTANTES //****************************** ********* ********************************** const int COUNT = 100 ; //Nombre d'éléments dans le tableau //**************************************** *********** ******************** // FONCTIONS ET PROCÉDURES //************ *********** ************************************** ** //****** ***************************************** * ******** // Vérifie si le nombre est premier // INPUT : N - nombre // SORTIE : TRUE - le nombre N est premier, FALSE - non premier //********** **************************************** **** bool IsPrimeNumber(int N) ( bool Res = true; switch (N) ( cas 0 : Res = false ; break ; cas 1 : Res = false ; break ; cas 2 : Res = true ; break ; cas 3 : Res = true ; break ; par défaut : pour (int je = 2; je

L'article aborde les concepts de nombres premiers et composés. Les définitions de ces nombres sont données avec des exemples. Nous apportons la preuve que le nombre de nombres premiers est illimité et nous l'inscrirons dans le tableau des nombres premiers en utilisant la méthode d'Eratosthène. Des preuves seront données pour déterminer si un nombre est premier ou composé.

Yandex.RTB R-A-339285-1

Nombres premiers et composés - Définitions et exemples

Les nombres premiers et composés sont classés comme entiers positifs. Ils doivent être supérieurs à un. Les diviseurs sont également divisés en simples et composites. Pour comprendre la notion de nombres composés, vous devez d'abord étudier les notions de diviseurs et de multiples.

Définition 1

Les nombres premiers sont des nombres entiers supérieurs à un et qui ont deux diviseurs positifs, c'est-à-dire eux-mêmes et 1.

Définition 2

Les nombres composés sont des nombres entiers supérieurs à un et comportant au moins trois diviseurs positifs.

Un n’est ni un nombre premier ni un nombre composé. Il n’a qu’un seul diviseur positif, il est donc différent de tous les autres nombres positifs. Tous les entiers positifs sont appelés nombres naturels, c'est-à-dire utilisés pour compter.

Définition 3

nombres premiers sont des nombres naturels qui n'ont que deux diviseurs positifs.

Définition 4

Nombre composé est un nombre naturel qui a plus de deux diviseurs positifs.

Tout nombre supérieur à 1 est premier ou composé. De la propriété de divisibilité, nous avons que 1 et le nombre a seront toujours diviseurs pour tout nombre a, c'est-à-dire qu'il sera divisible par lui-même et par 1. Donnons une définition des entiers.

Définition 5

Les nombres naturels qui ne sont pas premiers sont appelés nombres composés.

Nombres premiers : 2, 3, 11, 17, 131, 523. Ils ne sont divisibles que par eux-mêmes et 1. Nombres composés : 6, 63, 121, 6697. Autrement dit, le nombre 6 peut être décomposé en 2 et 3, et 63 en 1, 3, 7, 9, 21, 63 et 121 en 11, 11, c'est-à-dire que ses diviseurs seront 1, 11, 121. Le nombre 6697 se décompose en 37 et 181. Notez que les concepts de nombres premiers et de nombres premiers entre eux sont des concepts différents.

Pour faciliter l'utilisation des nombres premiers, vous devez utiliser un tableau :

Un tableau de tous les nombres naturels existants est irréaliste, car il y en a un nombre infini. Lorsque les nombres atteignent 10 000 ou 1 000 000 000, vous devriez alors envisager d’utiliser le tamis d’Ératosthène.

Considérons le théorème qui explique la dernière affirmation.

Théorème 1

Le plus petit diviseur positif autre que 1 d'un nombre naturel supérieur à un est un nombre premier.

Preuve 1

Supposons que a soit un nombre naturel supérieur à 1, b soit le plus petit diviseur non un de a. Il faut prouver que b est un nombre premier en utilisant la méthode des contradictions.

Supposons que b soit un nombre composé. De là, nous avons qu’il existe un diviseur pour b, qui est différent de 1 ainsi que de b. Un tel diviseur est noté b 1. Il faut que la condition 1< b 1 < b a été achevée.

De la condition, il ressort clairement que a est divisé par b, b est divisé par b 1, ce qui signifie que le concept de divisibilité s'exprime comme suit : a = bq et b = b 1 · q 1 , d'où a = b 1 · (q 1 · q) , où q et q1 sont des entiers. D'après la règle de multiplication des entiers, nous avons que le produit des entiers est un entier d'égalité de la forme a = b 1 · (q 1 · q) . On voit que b 1 est le diviseur du nombre a. Inégalité 1< b 1 < b Pas correspond, car on trouve que b est le plus petit diviseur positif et non-1 de a.

Théorème 2

Il existe un nombre infini de nombres premiers.

Preuve 2

Vraisemblablement, nous prenons un nombre fini d'entiers naturels n et les notons p 1, p 2,…, p n. Considérons la possibilité de trouver un nombre premier différent de ceux indiqués.

Prenons en considération le nombre p, qui est égal à p 1, p 2, ..., p n + 1. Il n'est pas égal à chacun des nombres correspondant aux nombres premiers de la forme p 1, p 2, ..., p n. Le nombre p est premier. Le théorème est alors considéré comme prouvé. S'il est composite, alors il faut prendre la notation p n + 1 et montrer que le diviseur ne coïncide avec aucun des p 1, p 2, ..., p n.

Si ce n'était pas le cas, alors, sur la base de la propriété de divisibilité du produit p 1, p 2, ..., p n , on trouve qu'il serait divisible par pn + 1. Notez que l'expression p n + 1 diviser le nombre p est égal à la somme p 1, p 2, ..., p n + 1. On obtient que l'expression p n + 1 Le deuxième terme de cette somme, qui vaut 1, doit être divisé, mais cela est impossible.

On voit que n’importe quel nombre premier peut être trouvé parmi n’importe quel nombre de nombres premiers donnés. Il s’ensuit qu’il existe une infinité de nombres premiers.

Comme il existe de nombreux nombres premiers, les tableaux se limitent aux nombres 100, 1 000, 10 000, etc.

Lors de l'élaboration d'un tableau de nombres premiers, vous devez tenir compte du fait qu'une telle tâche nécessite une vérification séquentielle des nombres, allant de 2 à 100. S'il n'y a pas de diviseur, il est enregistré dans le tableau ; s'il est composé, il n'est pas inscrit dans le tableau.

Regardons cela étape par étape.

Si vous commencez par le chiffre 2, alors il n'a que 2 diviseurs : 2 et 1, ce qui signifie qu'il peut être inscrit dans le tableau. Idem avec le chiffre 3. Le nombre 4 est composé, il doit être décomposé en 2 et 2. Le nombre 5 est premier, ce qui signifie qu'il peut être enregistré dans le tableau. Faites cela jusqu'au nombre 100.

Cette méthode est peu pratique et prend du temps. Il est possible de créer un tableau, mais cela demandera beaucoup de temps. Il est nécessaire d'utiliser des critères de divisibilité, ce qui accélérera le processus de recherche de diviseurs.

La méthode utilisant le tamis d'Eratosthène est considérée comme la plus pratique. Regardons les tableaux ci-dessous à titre d'exemple. Pour commencer, les nombres 2, 3, 4, ..., 50 sont écrits.

Vous devez maintenant rayer tous les nombres multiples de 2. Effectuez des barrés séquentiels. On obtient un tableau du type :

Nous passons à la barre des nombres multiples de 5. On a:

Rayez les nombres multiples de 7, 11. En fin de compte, le tableau ressemble à

Passons à la formulation du théorème.

Théorème 3

Le plus petit diviseur positif et différent de 1 du nombre de base a ne dépasse pas a, où a est la racine arithmétique du nombre donné.

Preuve 3

Il faut désigner b le plus petit diviseur d'un nombre composé a. Il existe un entier q, où a = b · q, et nous avons que b ≤ q. Les inégalités de forme sont inacceptables b > q, parce que la condition n'est pas respectée. Les deux côtés de l'inégalité b ≤ q doivent être multipliés par tout nombre positif b différent de 1. Nous obtenons que b · b ≤ b · q, où b 2 ≤ a et b ≤ a.

D'après le théorème éprouvé, il ressort clairement que rayer des nombres dans le tableau conduit au fait qu'il faut commencer par un nombre égal à b 2 et satisfaisant l'inégalité b 2 ≤ a. Autrement dit, si vous rayez les nombres multiples de 2, alors le processus commence par 4, et les multiples de 3 par 9, et ainsi de suite jusqu'à 100.

La compilation d’un tel tableau à l’aide du théorème d’Eratosthène suggère que lorsque tous les nombres composés sont barrés, il restera des nombres premiers qui ne dépassent pas n. Dans l’exemple où n = 50, nous avons que n = 50. De là, nous obtenons que le tamis d’Ératosthène élimine tous les nombres composés dont la valeur n’est pas supérieure à la valeur de la racine de 50. La recherche de numéros se fait en barrant.

Avant de résoudre, vous devez savoir si le nombre est premier ou composé. Des critères de divisibilité sont souvent utilisés. Regardons cela dans l'exemple ci-dessous.

Exemple 1

Montrer que le nombre 898989898989898989 est composé.

Solution

La somme des chiffres d'un nombre donné est 9 8 + 9 9 = 9 17. Cela signifie que le nombre 9 · 17 est divisible par 9, sur la base du test de divisibilité par 9. Il s’ensuit qu’il est composite.

De tels signes ne sont pas capables de prouver la primeur d’un nombre. Si une vérification est nécessaire, d'autres mesures doivent être prises. La méthode la plus appropriée consiste à énumérer des nombres. Au cours du processus, des nombres premiers et composés peuvent être trouvés. Autrement dit, les chiffres ne doivent pas dépasser une valeur. Autrement dit, le nombre a doit être factorisé en facteurs premiers. si cela est satisfait, alors le nombre a peut être considéré comme premier.

Exemple 2

Déterminez le nombre composé ou premier 11723.

Solution

Vous devez maintenant trouver tous les diviseurs du nombre 11723. Besoin d'évaluer 11723 .

De là, nous voyons que 11723< 200 , то 200 2 = 40 000 , et 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Pour une estimation plus précise du nombre 11723, il faut écrire l'expression 108 2 = 11 664, et 109 2 = 11 881 , Que 108 2 < 11 723 < 109 2 . Il s'ensuit que 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

En développant, nous constatons que 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 , 101 , 103 , 107 sont tous des nombres premiers. L’ensemble de ce processus peut être représenté comme une division par colonne. Autrement dit, divisez 11723 par 19. Le nombre 19 est l'un de ses facteurs, puisqu'on obtient une division sans reste. Représentons la division sous forme de colonne :

Il s'ensuit que 11723 est un nombre composé, car en plus de lui-même et de 1, il possède un diviseur de 19.

Répondre: 11723 est un nombre composé.

Si vous remarquez une erreur dans le texte, veuillez la surligner et appuyer sur Ctrl+Entrée

La réponse d'Ilya est correcte, mais pas très détaillée. Au XVIIIe siècle, d’ailleurs, un était encore considéré comme un nombre premier. Par exemple, de grands mathématiciens comme Euler et Goldbach. Goldbach est l'auteur de l'un des sept problèmes du millénaire : l'hypothèse de Goldbach. La formulation originale stipule que tout nombre pair peut être représenté comme la somme de deux nombres premiers. D’ailleurs, initialement 1 était pris en compte comme nombre premier, et on voit ceci : 2 = 1+1. Il s’agit du plus petit exemple qui satisfait à la formulation originale de l’hypothèse. Plus tard, elle a été corrigée et la formulation a acquis une forme moderne : « tout nombre pair, commençant par 4, peut être représenté comme la somme de deux nombres premiers ».

Rappelons la définition. Un nombre premier est un nombre naturel p qui n'a que 2 diviseurs naturels différents : p lui-même et 1. Corollaire de la définition : un nombre premier p n'a qu'un seul diviseur premier - p lui-même.

Supposons maintenant que 1 soit un nombre premier. Par définition, un nombre premier n’a qu’un seul diviseur premier : lui-même. Il s'avère alors que tout nombre premier supérieur à 1 est divisible par un nombre premier différent de lui (par 1). Mais deux nombres premiers différents ne peuvent pas être divisés l'un par l'autre, car sinon ce ne sont pas des nombres premiers, mais des nombres composés, ce qui contredit la définition. Avec cette approche, il s’avère qu’il n’existe qu’un seul nombre premier : l’unité elle-même. Mais c'est absurde. Donc 1 n’est pas un nombre premier.

1, ainsi que 0, forment une autre classe de nombres – la classe des éléments neutres par rapport aux opérations n-aires dans un sous-ensemble du champ algébrique. De plus, en ce qui concerne l'opération d'addition, 1 est également un élément générateur de l'anneau des nombres entiers.

Compte tenu de cela, il n’est pas difficile de découvrir des analogues de nombres premiers dans d’autres structures algébriques. Supposons que nous ayons un groupe multiplicatif formé de puissances de 2, à partir de 1 : 2, 4, 8, 16, ... etc. 2 agit ici comme un élément formateur. Un nombre premier de ce groupe est un nombre supérieur au plus petit élément et divisible uniquement par lui-même et par le plus petit élément. Dans notre groupe, seuls 4 possèdent de telles propriétés. Il n'y a plus de nombres premiers dans notre groupe.

Si 2 était également un nombre premier dans notre groupe, alors voyez le premier paragraphe - encore une fois, il s'avérerait que seul 2 est un nombre premier.

Les nombres sont différents : naturels, rationnels, rationnels, entiers et fractionnaires, positifs et négatifs, complexes et premiers, impairs et pairs, réels, etc. À partir de cet article, vous pourrez découvrir ce que sont les nombres premiers.

Quels nombres sont appelés « simples » en anglais ?

Très souvent, les écoliers ne savent pas comment répondre à première vue à l'une des questions les plus simples en mathématiques, à savoir ce qu'est un nombre premier. Ils confondent souvent les nombres premiers avec les nombres naturels (c'est-à-dire les nombres que les gens utilisent pour compter des objets, alors que dans certaines sources, ils commencent par zéro et dans d'autres par un). Mais ce sont deux concepts complètement différents. Les nombres premiers sont des nombres naturels, c'est-à-dire des nombres entiers et positifs supérieurs à un et qui n'ont que 2 diviseurs naturels. De plus, l'un de ces diviseurs est le nombre donné et le second est un. Par exemple, trois est un nombre premier car il ne peut être divisé sans reste par un nombre autre que lui-même et un.

Nombres composés

Le contraire des nombres premiers sont les nombres composés. Ils sont aussi naturels, également supérieurs à un, mais n'ont pas deux, mais un plus grand nombre de diviseurs. Ainsi, par exemple, les nombres 4, 6, 8, 9, etc. sont des nombres naturels, composés, mais non premiers. Comme vous pouvez le constater, ce sont pour la plupart des nombres pairs, mais pas tous. Mais « deux » est un nombre pair et le « premier nombre » d’une série de nombres premiers.

Sous-séquence

Pour construire une série de nombres premiers, il faut choisir parmi tous les nombres naturels, en tenant compte de leur définition, c'est-à-dire qu'il faut agir par contradiction. Il est nécessaire d’examiner chacun des nombres naturels positifs pour voir s’il a plus de deux diviseurs. Essayons de construire une série (séquence) composée de nombres premiers. La liste commence par deux, suivi de trois, puisqu'elle n'est divisible que par elle-même et par un. Considérez le chiffre quatre. A-t-il des diviseurs autres que quatre et un ? Oui, ce nombre est 2. Donc quatre n’est pas un nombre premier. Cinq est également premier (il n'est divisible par aucun autre nombre, sauf 1 et 5), mais six est divisible. Et en général, si vous suivez tous les nombres pairs, vous remarquerez qu’à l’exception de « deux », aucun d’entre eux n’est premier. On en conclut que les nombres pairs, sauf deux, ne sont pas premiers. Autre découverte : tous les nombres divisibles par trois, sauf le trois lui-même, qu'ils soient pairs ou impairs, ne sont pas non plus premiers (6, 9, 12, 15, 18, 21, 24, 27, etc.). Il en va de même pour les nombres divisibles par cinq et sept. Toute leur multitude n’est pas non plus simple. Résumons. Ainsi, les nombres simples à un chiffre incluent tous les nombres impairs sauf un et neuf, et même « deux » sont des nombres pairs. Les dizaines elles-mêmes (10, 20,... 40, etc.) ne sont pas simples. Les nombres premiers à deux chiffres, à trois chiffres, etc. peuvent être déterminés sur la base des principes ci-dessus : s'ils n'ont pas de diviseurs autres qu'eux-mêmes et un.

Théories sur les propriétés des nombres premiers

Il existe une science qui étudie les propriétés des nombres entiers, y compris les nombres premiers. Il s'agit d'une branche des mathématiques appelée supérieure. Outre les propriétés des nombres entiers, elle traite également des nombres algébriques et transcendantaux, ainsi que des fonctions d'origines diverses liées à l'arithmétique de ces nombres. Dans ces études, outre les méthodes élémentaires et algébriques, des méthodes analytiques et géométriques sont également utilisées. Plus précisément, la « Théorie des nombres » traite de l’étude des nombres premiers.

Les nombres premiers sont les « éléments constitutifs » des nombres naturels

En arithmétique, il existe un théorème appelé théorème fondamental. Selon lui, tout nombre naturel, sauf un, peut être représenté comme un produit dont les facteurs sont des nombres premiers, et l'ordre des facteurs est unique, ce qui signifie que la méthode de représentation est unique. C’est ce qu’on appelle factoriser un nombre naturel en facteurs premiers. Il existe un autre nom pour ce processus : la factorisation des nombres. Sur cette base, les nombres premiers peuvent être appelés « matériaux de construction », « blocs » pour construire des nombres naturels.

Recherchez des nombres premiers. Tests de simplicité

De nombreux scientifiques de différentes époques ont essayé de trouver des principes (systèmes) permettant de trouver une liste de nombres premiers. La science connaît des systèmes appelés tamis Atkin, tamis Sundartham et tamis Eratosthène. Cependant, ils ne produisent aucun résultat significatif et un simple test est utilisé pour trouver les nombres premiers. Les mathématiciens ont également créé des algorithmes. Ils sont généralement appelés tests de primalité. Par exemple, il existe un test développé par Rabin et Miller. Il est utilisé par les cryptographes. Il existe également le test Kayal-Agrawal-Sasquena. Cependant, malgré une précision suffisante, son calcul est très difficile, ce qui réduit son importance pratique.

L’ensemble des nombres premiers a-t-il une limite ?

Le scientifique grec Euclide a écrit dans son livre « Éléments » que l’ensemble des nombres premiers est l’infini. Il a dit ceci : « Imaginons un instant que les nombres premiers aient une limite. Ensuite, multiplions-les entre eux et ajoutons-en un au produit. Le nombre obtenu à la suite de ces actions simples ne peut être divisé par aucune des séries de nombres premiers, car le reste sera toujours un. Cela signifie qu'il existe un autre nombre qui n'est pas encore inclus dans la liste des nombres premiers. Par conséquent, notre hypothèse n’est pas vraie et cet ensemble ne peut pas avoir de limite. Outre la preuve d'Euclide, il existe une formule plus moderne donnée par le mathématicien suisse du XVIIIe siècle Leonhard Euler. Selon lui, la somme réciproque de la somme des n premiers nombres croît de manière illimitée à mesure que le nombre n augmente. Et voici la formule du théorème concernant la distribution des nombres premiers : (n) croît comme n/ln (n).

Quel est le plus grand nombre premier ?

Le même Leonard Euler a pu trouver le plus grand nombre premier de son époque. Il s'agit de 2 31 - 1 = 2147483647. Cependant, en 2013, un autre nombre premier le plus précis de la liste des nombres premiers a été calculé - 2 57885161 - 1. Il s'appelle le nombre de Mersenne. Il contient environ 17 millions de chiffres décimaux. Comme vous pouvez le constater, le nombre trouvé par un scientifique du XVIIIe siècle est plusieurs fois inférieur à celui-ci. Il aurait dû en être ainsi, car Euler effectuait ce calcul manuellement, alors que notre contemporain était probablement aidé par un ordinateur. De plus, ce numéro a été obtenu à la Faculté de mathématiques de l'un des départements américains. Les nombres portant le nom de ce scientifique réussissent le test de primalité de Luc-Lemaire. Mais la science ne veut pas s’arrêter là. L'Electronic Frontier Foundation, fondée en 1990 aux États-Unis d'Amérique (EFF), offre une récompense monétaire pour la découverte de grands nombres premiers. Et si jusqu'en 2013 le prix était décerné aux scientifiques qui les trouveraient entre 1 et 10 millions de nombres décimaux, aujourd'hui ce chiffre atteint entre 100 millions et 1 milliard. Les prix varient de 150 à 250 000 dollars américains.

Noms de nombres premiers spéciaux

Les nombres qui ont été trouvés grâce à des algorithmes créés par certains scientifiques et qui ont réussi le test de simplicité sont appelés spéciaux. En voici quelques uns:

1. Merssen.

4. Cullen.

6. Mills et coll.

La simplicité de ces nombres, nommés d'après les scientifiques ci-dessus, est établie à l'aide des tests suivants :

1. Luc-Lemaire.

2. Pépina.

3. Riesel.

4. Billhart - Lemaire - Selfridge et autres.

La science moderne ne s’arrête pas là et, probablement, dans un avenir proche, le monde connaîtra les noms de ceux qui ont réussi à remporter le prix de 250 000 $ en trouvant le plus grand nombre premier.

Énumération des diviseurs. Par définition, le nombre n n'est premier que s'il n'est pas divisible également par 2 et d'autres entiers sauf 1 et lui-même. La formule ci-dessus supprime les étapes inutiles et fait gagner du temps : par exemple, après avoir vérifié si un nombre est divisible par 3, il n'est pas nécessaire de vérifier s'il est divisible par 9.

• La fonction floor(x) arrondit x à l'entier le plus proche inférieur ou égal à x.

Apprenez-en davantage sur l’arithmétique modulaire. L'opération « x mod y » (mod est une abréviation du mot latin « modulo », c'est-à-dire « module ») signifie « diviser x par y et trouver le reste ». En d’autres termes, en arithmétique modulaire, lorsqu’on atteint une certaine valeur, appelée module, les chiffres « reviennent » à nouveau à zéro. Par exemple, une horloge donne l'heure avec un module 12 : elle affiche 10, 11 et 12 heures puis revient à 1.

• De nombreuses calculatrices ont une touche mod. La fin de cette section montre comment évaluer manuellement cette fonction pour de grands nombres.

Découvrez les pièges du petit théorème de Fermat. Tous les nombres pour lesquels les conditions de test ne sont pas remplies sont composites, mais les nombres restants ne sont que probablement sont classés comme simples. Si vous souhaitez éviter des résultats incorrects, recherchez n dans la liste des « nombres de Carmichael » (nombres composés qui satisfont à ce test) et des « nombres de Fermat pseudo-premiers » (ces nombres ne répondent aux conditions du test que pour certaines valeurs un).

Si cela vous convient, utilisez le test de Miller-Rabin. Bien que cette méthode soit assez lourde à calculer manuellement, elle est souvent utilisée dans les programmes informatiques. Elle offre une vitesse acceptable et produit moins d'erreurs que la méthode de Fermat. Un nombre composé ne sera pas accepté comme nombre premier si les calculs sont effectués pour plus du quart des valeurs. un. Si vous sélectionnez différentes valeurs au hasard un et pour tous, le test donnera un résultat positif, nous pouvons supposer avec un degré de confiance assez élevé que n est un nombre premier.

Pour les grands nombres, utilisez l’arithmétique modulaire. Si vous n'avez pas de calculatrice avec mod sous la main, ou si votre calculatrice n'est pas conçue pour gérer des nombres aussi grands, utilisez les propriétés des puissances et de l'arithmétique modulaire pour faciliter les calculs. Ci-dessous un exemple pour 3 50 (\style d'affichage 3^(50)) module 50 :

• Réécrivez l'expression sous une forme plus pratique : mod 50. Lors de calculs manuels, des simplifications supplémentaires peuvent être nécessaires.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Ici nous avons pris en compte la propriété de multiplication modulaire.
• 3 25 (\style d'affichage 3^(25)) module 50 = 43.
• (3 25 (\style d'affichage (3^(25)) module 50 * 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 * 43) (\displaystyle (43*43)) modèle 50.
• = 1849 (\ displaystyle = 1849) modèle 50.
• = 49 (\ displaystyle = 49).