L'univers et nous Index du Forum
L'univers et nous
fondé par Thomas le 24 août 2010
 
L'univers et nous Index du ForumFAQRechercherS’enregistrerConnexion

:: Les nombres premiers ::

 
Poster un nouveau sujet   Répondre au sujet    L'univers et nous Index du Forum -> Théories -> Mathématiques
Sujet précédent :: Sujet suivant  
Auteur Message
Thomas
Administrateur

Hors ligne

Inscrit le: 24 Aoû 2010
Messages: 55
Localisation: Perdu dans le réseau électronique...
Masculin

MessagePosté le: Mer 23 Mar - 01:07 (2011)    Sujet du message: Les nombres premiers Répondre en citant

Bonjour à tous !

Je lance cette discussion, plutôt qu'un débat, sur les nombres premiers, qui me passionnent.

Pour information :
Les nombres premiers sont des nombres qui ne sont divisibles que par 1 et par eux-mêmes, en nombres entiers.

Voici une petite liste des premiers nombres premiers ^^ :

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47...

C'est relativement simple, apparemment, mais personne n'a réellement trouvé de formule pour les calculer tous.
A chaque fois, soit le temps de recherche est exponentiel avec la grandeur du nombre testé, soit la formule ne fonctionne que pour certains nombres premiers, et fait encore des erreurs.
Celui qui trouvera la formule des nombres premiers, pourra s'estimer heureux, et remporter de nombreux prix mathématiques, d'après ce que j'ai pu entendre.

Il est d'ailleurs dit que si vous trouvez un nombre premier avec au moins cent millions de chiffres décimaux, vous pouvez gagner 100 000 $ USD. Pas mal, non ?

Il existe une méthode très simple qui permet de tous les lister :
A chaque nombre, il faut le diviser par tous les nombres entiers inférieurs à celui-ci, en excluant 1 et les nombres négatifs. (ça fonctionne, mais c'est inutile).
Cette méthode est la plus simple mais peut être largement optimisée :
-on peut ne diviser que par les nombres premiers trouvés, car un nombre non premier est forcément composé d'autres nombres, qui à la source sont premiers. Exemple : 16 est divisible par 4, et forcément par 2. Au lieu de tester la division par 4, on ne teste que celle par 2 pour découvrir que 16 n'est pas premier.
-on peut s'arrêter une fois que l'on a atteint la racine carré du nombre testé. En effet, tout nombre supérieur à celle-ci ne fonctionnerait pas. Exemple : la racine carré de 9 est 3. 9 n'est pas divisible par deux. 9 est divisible par 3, donc on a pas besoin de continuer avec 4, 5, 6, 7 et 8. Car 9 n'est pas divisible par ces nombres.

Il existe évidement bien d'autres méthodes pour optimiser le calcul, mais dans tous les cas, plus le nombre est grand, plus le nombre de calculs s'agrandit.

Hier et aujourd'hui, j'ai utilisé une calculette programmable pas très puissante (Casio 35+), et j'ai pu trouvé un peu plus de 1000 nombres premiers grâce à cette méthode de calcul. Le dernier sur la liste était 8429. Mais j'ai du la laisser allumée toute la nuit, et les piles sont mortes ^^.
Je vous demande donc si ce sujet vous intéresse, si vous avez trouvé une méthode plus efficace, si vous avec quelques questions, et quelques réponses.

J'ai prévu de transmettre le programme sur ordinateur, pour voir jusqu'à combien il peu aller, et en combien de temps.
_________________
Merci de votre lecture !
Revenir en haut
Publicité






MessagePosté le: Mer 23 Mar - 01:07 (2011)    Sujet du message: Publicité

PublicitéSupprimer les publicités ?
Revenir en haut
Mr. Science


Hors ligne

Inscrit le: 23 Fév 2011
Messages: 19
Localisation: Champ de probabilité de présence très étendu
Masculin

MessagePosté le: Mer 23 Mar - 15:18 (2011)    Sujet du message: Les nombres premiers Répondre en citant

Tu utilises en gros le principe d'Erastothène, classique.

Renseigne toi sur le crible de Sundaram, tu pourras ainsi exclure un bon nombre de nombres premiers, en plus des nombres pairs, que tu as déjà dû éliminer de tes calculs, il ne devrais rester que peu de nombres à examiner ensuite.
Le crible de Sundaram fonctionne ainsi : Soit In = 2n +1 et Im = 2m +1.
Suite à quelque calculs ( Im = 2n + 1 + 2k ), on parvient, en variant  k et n, à trouver l'ensemble des produits de deux nombres impairs, chose ardue sans ce genre de méthode, et ralentissant considérablement les programmes.

Ce crible est simplifié par le tableau non exhaustif suivant ( qui se simplifie au fur et à mesure, les premières lignes étant plus complexes à calculer, en effet)
9
1525
213549
27456381
33557799121
396591117143169

_________________
Six sens en science sans scie-anse !
Revenir en haut
Thomas
Administrateur

Hors ligne

Inscrit le: 24 Aoû 2010
Messages: 55
Localisation: Perdu dans le réseau électronique...
Masculin

MessagePosté le: Jeu 24 Mar - 18:51 (2011)    Sujet du message: Les nombres premiers Répondre en citant

Par contre, je me suis rendu compte d'une erreur de ma part ^^
s'arrêter à la racine carré du nombre testé n'est pas judicieux...
Si on prend 10 par exemple, sa racine carré est environ 3.16. même si je teste les nombres jusqu'à quatre (donc 2 et 3),
il reste que 10 est encore divisible par 5, et que je ne l'ai pas testé.

N'étant qu'en seconde, je ne suis pas super fort en maths (je gère au niveau de ma classe, mais après...).
Alors, est-ce que quelqu'un de mieux qualifié que moi pourrait me dire si c'est vraiment judicieux de s'arrêter à la racine ?

De même, je n'ai pas bien compris tes calculs Mr. Science... Qu'est-ce que Im, In ?
Je pense avoir compris que l'on part de deux nombres impairs, et qu'on cherche à vérifier s'ils ont des diviseurs communs, ou quelque chose dans le genre... Enfin, peut-tu m'expliquer ça plus en détails s'il te plait ? ^^

Par contre, tu me parle d'eliminer des nombres premiers des calculs... Mais pour tester un nombre, il faut bien le diviser par tous les nombres premiers inférieurs non ? (en s'arrêtant peut-être à la moitié ?) Si on en enlève, on n'est pas sur de pouvoir tester le nombre...
_________________
Merci de votre lecture !
Revenir en haut
Mr. Science


Hors ligne

Inscrit le: 23 Fév 2011
Messages: 19
Localisation: Champ de probabilité de présence très étendu
Masculin

MessagePosté le: Jeu 24 Mar - 22:46 (2011)    Sujet du message: Les nombres premiers Répondre en citant

 
Citation:
Par contre, je me suis rendu compte d'une erreur de ma part ^^
s'arrêter à la racine carré du nombre testé n'est pas judicieux...
Si on prend 10 par exemple, sa racine carré est environ 3.16. même si je teste les nombres jusqu'à quatre (donc 2 et 3),
il reste que 10 est encore divisible par 5, et que je ne l'ai pas testé.


Peu importe, le 2 nous suffit pour savoir que 10 n'est pas premier, tu sais sûrement que x = (nombre inférieur ou égal à x/2) *(nombre inférieur ou égal à x/2)


 
Citation:

De même, je n'ai pas bien compris tes calculs Mr. Science... Qu'est-ce que Im, In ?

Ce sont des nombres impairs quelconques.

 
Citation:

Enfin, peut-tu m'expliquer ça plus en détails s'il te plait ?

Très certainement, par où commencer :

On a Im et In, nombres premiers impairs.
On veut calculer tous les nombres impairs non premier, les nombres plus complexes simplifier sont, comme le savent les cryptologues, ceux issus de deux nombres premiers.
Un nombre impair s'écrit sous la forme 2 x+1, j'imagine que tu le sais.

Donc In = 2n + 1 = 2m + 1 + 2 x  ( par exemple, avec 11 et 5 : 11 = 2 * 2 + 1 + 2 * 3 )
Donc produit de Im * In =  ( 2 n + 1 ) ² + x ( 4n +2 )

Voilà, en variant x et n, on connait tous les nombres impairs non premiers, car issus de deux nombres premiers. On les place ensuite dans un tableau si nécessaire.

Je peux pas faire plus simple.


 
Citation:

Par contre, tu me parle d'eliminer des nombres premiers des calculs... Mais pour tester un nombre, il faut bien le diviser par tous les nombres premiers inférieurs non ?

Je voulais dire nombres impairs, je me suis fourvoyé.
_________________
Six sens en science sans scie-anse !
Revenir en haut
Thomas
Administrateur

Hors ligne

Inscrit le: 24 Aoû 2010
Messages: 55
Localisation: Perdu dans le réseau électronique...
Masculin

MessagePosté le: Ven 25 Mar - 12:42 (2011)    Sujet du message: Les nombres premiers Répondre en citant

D'accord, je pense avoir compris, merci.
En fait, le but est d'éliminer d'office certains nombres qui peuvent paraitre premiers, et ainsi éviter des tests inutiles.
Mr. Science a écrit:
Donc In = 2n + 1 = 2m + 1 + 2 x  ( par exemple, avec 11 et 5 : 11 = 2 * 2 + 1 + 2 * 3 )
Donc produit de Im * In =  ( 2 n + 1 ) ² + x ( 4n +2 )

Voilà, en variant x et n, on connait tous les nombres impairs non premiers, car issus de deux nombres premiers. On les place ensuite dans un tableau si nécessaire.

Ici, je comprend à quoi correspondent Im (nombre impair déterminé par 2m+1) et In (nombre impair déterminé par 2n+1). Mais c'est le x, que tu remplace par 3 qui m'intrigue... Ce n'est pas n (qui est égal à 5 dans ton exemple) ni m (égal à 2). Il ne s'agit pas non plus de In (11) ou de In (5). Serait-ce m+1 ? Ce serait bizarre... Ne suffirait-il pas de faire Im*In pour trouver leur produit ? On part avec Im=3, puis on augmente n au fur et à mesure.


Par contre, pour la racine carré, je me disais bien que 10 avait été jugé non premier grâce à la division par deux.
Mais je me demandais si pour certains nombres, s'arrêter à la racine empêchait de tester d'autres diviseurs.

Après quelques réflexions, je me suis dis que ça allait :

la racine carré est le seul cas où les diviseurs sont communs. logique, racine de 4 = 2*2 ^^

donc, tout diviseur supérieur à a racine va forcément de paire avec une diviseur inférieur à la racine.
racine de 36=6
36/9=4. Sauf que 9>6, donc on n'est pas censé le tester.
36/18=2. Sauf que 18>6, et de même que pour 9, on ne teste pas ce nombre.
Même si 9 et 18 ne sont pas testés, étant plus grand que la racine de 36 (6), le second diviseur qui leur est lié est forcément inférieur à 6.
Donc on est obligé de les tester, et 9 et 18 deviennent inutiles.

Maintenant, si je rajoute en plus la règle suivante :
Ne tester que les diviseurs déjà premiers, car les autres en sont forcément composés.
Et bien le temps de calcul est largement réduit.
Ma méthode de la racine carré était juste, mais pas mon raisonnement au départ ^^
_________________
Merci de votre lecture !
Revenir en haut
Contenu Sponsorisé






MessagePosté le: Aujourd’hui à 22:57 (2018)    Sujet du message: Les nombres premiers

Revenir en haut
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    L'univers et nous Index du Forum -> Théories -> Mathématiques Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  

Index | Creer un forum | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation
Texno x0.3 © theme by Larme D'Ange 2006
Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com