Aller au contenu
C8H10N4O2

Nombre Premier

Messages recommandés

Bonsoir à tous ,

Je me souviens de ma scolarité de cet algorithme pour déterminer si un nombre est premier : s'il n'est multiple ni de 2, ni de 3, ni de 5, le diviser successivement par les nombres premiers suivants. Dès que le quotient trouvé est inférieur au diviseur, on s'arrête et on peut affirmer que le nombre est premier.

Ex : 127 n'est pas divisible par 2, ni par 3, ni par 5.  127= 7*18+1 et 18>7, donc on recommence ...jusqu'à 127 = 13*9 + 10 , et 9<13 donc on peut affirmer que 127 est premier.

Quelqu'un a-t-il une idée de la manière dont on justifie / démontre la validité de cet algorithme ?

Partager ce message


Lien à poster
Partager sur d’autres sites
Il y a 2 heures, pzorba75 a dit :

Par la commutativité de la multiplication, tout simplement.

Je ne comprends pas bien, par exemple en disant que 127 = 13*9 + 10 <=>  127 = 9*13 + 10 ?  

Partager ce message


Lien à poster
Partager sur d’autres sites

Salut,

 

Avec des mots.

si tu divises 127 par 3, 5 , 7 , ... et que ces divisions (par des nombres premiers successifs) ne donne aucune un résultat entier, c'est que 127 n'est pas divisible par 3, 5 , 7 ...

quand faut-il s'arrêter ?

V127 = 11,26...

Si on divise 127 par un nombre premier >= V127 = 11,26... (donc 13 , 17 , 19 ...), le résultat de la division est forcément inférieur à V127 = 11,26...

Et donc si 127 était divisible par un nombre premier > V127, il serait divisible par le résultat de la division qui serait un nombre entier < V127 ...
Mais l'algorithme a déjà essayé de diviser 127 par les nombres premier < V127 et donc si on n'a pas trouvé de diviseurs premiers < V127, il n'y a aura pas non plus de diviseurs premiers de 127 > V127
 

 

 

Partager ce message


Lien à poster
Partager sur d’autres sites
il y a 16 minutes, Black Jack a dit :

Salut,

 

Avec des mots.

si tu divises 127 par 3, 5 , 7 , ... et que ces divisions (par des nombres premiers successifs) ne donne aucune un résultat entier, c'est que 127 n'est pas divisible par 3, 5 , 7 ...

quand faut-il s'arrêter ?

V127 = 11,26...

Si on divise 127 par un nombre premier >= V127 = 11,26... (donc 13 , 17 , 19 ...), le résultat de la division est forcément inférieur à V127 = 11,26...

Et donc si 127 était divisible par un nombre premier > V127, il serait divisible par le résultat de la division qui serait un nombre entier < V127 ...
Mais l'algorithme a déjà essayé de diviser 127 par les nombres premier < V127 et donc si on n'a pas trouvé de diviseurs premiers < V127, il n'y a aura pas non plus de diviseurs premiers de 127 > V127
 

 

 

J'ai compris, merci beaucoup !

Partager ce message


Lien à poster
Partager sur d’autres sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Invité
Répondre à ce sujet…

×   Collé en tant que texte enrichi.   Coller en tant que texte brut à la place

  Seulement 75 émoticônes maximum sont autorisées.

×   Votre lien a été automatiquement intégré.   Afficher plutôt comme un lien

×   Votre contenu précédent a été rétabli.   Vider l’éditeur

×   Vous ne pouvez pas directement coller des images. Envoyez-les depuis votre ordinateur ou insérez-les depuis une URL.

Chargement

×
×
  • Créer...