Sciences & Technologies

Quelqu´un saurait-il comment font les ordinateurs pour calculer des nombres premiers? Doivent-ils tester tous les nombres les uns après les autres ou bien existe-t-il une astuce pour connaître à peu de choses près la valeur d´un nombre premier?

on ne peut connaitre à peu près la valeur d´un nombre premier. soit C´EST un nombre premier, soit CA N´EST PAS un nombre premier
sinon, la manière dont ils les calculent, j´en sais rien du tout. j´aurai dit qu´ils essayent fde les diviser par d´autres nombres premiers, mais il doit y avoir un autre moyen.

J´ai lu un truc là dessus y´a pas longtemps, en fait ils ne peuvent pas. Ils ne peuvent que générer des nombres pseudo-premiers, il ne faut pas prendre le mot ´pseudo´ au sens premiere, ce ne sont pas de faux premiers, mais des premiers dont on a pas la certitude qu´ils soient premiers :
http://fr2.php.net/manual/fr/function.gmp-prob-prime.php
Sinon tu as cette fonction :
http://www.asp-php.net/ressources/bouts_de_code.aspx?id=701
(ça me semble pas trop difficile à comprendre).
En gros on prend chaque nombre, on le divise par 3, 2 (puis 7 c´est mieux !) , et si ce nombre divisé par 3, 2, 7 donne un entier à chaque fois, alors il est probablement premier, et ainsi de suite pour l´autre nombre.
Mais je pense que la marge d´erreur est très très faible.

errata
"et si ce nombre divisé par 3, 2, 7 donne un entier à chaque fois, alors il est probablement premier"

"et si ce nombre divisé par 3, 2, 7 donne toujours un décimal, alors il est probablement premier.

Par contre, il existe sûrement un algorithme qui permet de déterminer si le nombre est strictement premier. Enfin je suppose. Mais tester ça pour tous les nombres surchargerait sûrement tout le système.
Tiens :
http://fr.wikipedia.org/wiki/Nombres_premiers#Algorithmes

bah, ils le font pas en même temps.
sinon, pour la deuxieme méthode, c´est pas mal, mais pas assez précis pour les ordinateurs.

"Quelqu´un saurait-il comment font les ordinateurs pour calculer des nombres premiers? Doivent-ils tester tous les nombres les uns après les autres ou bien existe-t-il une astuce pour connaître à peu de choses près la valeur d´un nombre premier?"

Si on a besoin d´énumérer des nombres premiers, on peut utiliser les techniques de cribles présenter sur wikipedia. Ce ne sont pas les plus performantes que l´on connaisse, mais l´idée est la.

Pour générer de grand nombre premier, un logiciels peut tirer de grandes chaines de bits aléatoires. Ils vérifient ensuite si l´entier qui est représenté ainsi est premier ou non.

On en vient a la question: comment sait on qu´un nombre est premier. Cette question était une question difficile jusqu´en 2000. On connait depuis un algorithme polynomial (comprendre efficace) qui permet de savoir si un nombre est premier ou composé. Ce qui est assez frustrant est que l´algorithme peut assurer qu´un nombre n´est pas premier mais ne sait pas donner une décomposition en facteur premier du nombre. Ce dernier problème reste "difficile".

"Par contre, il existe sûrement un algorithme qui permet de déterminer si le nombre est strictement premier. Enfin je suppose. Mais tester ça pour tous les nombres surchargerait sûrement tout le système."
Bah compte tenu qu´il y a une infifnité de nombre premier, j´imagine bien que ca surcagerait tous les systèmes du monde !

Le principal projet actuel et depuis effectivement 2000 utilise le crible de Marin Mersenne*, moine français du 15ème siècle qui passait son temps à vérifier des nombres premiers, et toute personne avec un ordinateur peut participer à ce projet collaboratif appelé par son acronyme GIMPS Great Internet 📶 Mersenne Prime Search
https://www.mersenne.org/download/

• En mathématiques et plus précisément en arithmétique, un nombre de Mersenne est un nombre de la forme 2n moins 1 (souvent noté Mn ), où n est un entier naturel non nul ; un nombre de Mersenne premier (ou nombre premier de Mersenne) est donc un nombre premier de cette forme.

https://fr.m.wikipedia.org wiki
Nombre de Mersenne premier

Une fois le client Prime95 installé, vous pouvez lancer un benchmark, qui sur ma machine actuelle donne :

Speed 2895 Mhz

Voire un torture test pour pousser votre appareil à fond, donc le ralentir à bloc pendant toute la durée du test...

Si vous n'utilisez pas votre ordinateur, c'est intéressant, sinon, ça le ralentit, quelle que soit sa puissance, les nombres premiers étant infinis, comme les autres nombres.

D'ailleurs c'est intéressant, car il y a moins de nombres premiers que de nombres :

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

23 premiers dans les cent premiers nombres, 21 dans les cent suivants (101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197 et 199), mais seulement 16 entre 211 et 293, comme entre 307 et 397, et 17 entre 401 et 499.

Donc 93 nombres premiers entre 2 et 499, 18,6% des cinq cents premiers nombres.

Et probablement moins encore des mille premiers nombres, effectivement, 75 premiers entre 503 et 996, donc 168 premiers en dessous de mille, entre 0 et 1000, soit 16,8%.

Et leur répartition baisse encore après mille.

Donc les nombres premiers sont beaucoup moins nombreux que les nombres, et pourtant les deux sont infinis, il y a donc des infinis plus réduits que d'autres !

Le fait que les nombres de Mersenne premiers soient très réduits, seulement 51 connus à ce jour, tendrait vers l'hypothèse qu'ils ne soient pas infinis, mais pour le calculer, il faudra des ordinateurs quantiques, car pour l'instant c'est trop long

Le 24 mars 2024 à 10:00:55 :
Si vous n'utilisez pas votre ordinateur, c'est intéressant, sinon, ça le ralentit, quelle que soit sa puissance, les nombres premiers étant infinis, comme les autres nombres.

D'ailleurs c'est intéressant, car il y a moins de nombres premiers que de nombres :

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

23 premiers dans les cent premiers nombres, 21 dans les cent suivants (101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197 et 199), mais seulement 16 entre 211 et 293, comme entre 307 et 397, et 17 entre 401 et 499.

Donc 93 nombres premiers entre 2 et 499, 18,6% des cinq cents premiers nombres.

Et probablement moins encore des mille premiers nombres, effectivement, 75 premiers entre 503 et 996, donc 168 premiers en dessous de mille, entre 0 et 1000, soit 16,8%.

Et leur répartition baisse encore après mille.

Donc les nombres premiers sont beaucoup moins nombreux que les nombres, et pourtant les deux sont infinis, il y a donc des infinis plus réduits que d'autres !

certes il y a plusieurs infinis mais celui des nombres premier est le même que celui des entiers naturels car tu peux établir une bijection entre les deux ce que l'ont fait tous le temps quand on note les nombres premiers "Pn" avec "n" entier naturel