Problème sur facteurs premiers ?

Problème sur facteurs premiers ?
Message de airlibre posté le 27-02-2020 à 11:11:26 (S | E | F)
Bonjour,

Sur un problème de décomposition d'un nombre en facteurs premiers,
j'ai séché sur celui-ci : 12321 (!!??)
j'ai bien trouvé 3^2 pour le premier, mais pas pour le suivant.
Après avoir regardé la solution, il se trouve que le suivant en question était 37^2 !!!....
Question :
y aurait-il une méthode pour trouver le nombre premier de divisibilité dans ce type de problème ?,
car il est assez pénible de rechercher tous les premiers les uns après les autres jusqu'au bon, surtout, par exemple,
si on doit rechercher un premier très haut tel que 11579 ou plus !!!...

Merci

---

Réponse : Problème sur facteurs premiers ? de wab51, postée le 27-02-2020 à 14:42:29 (S | E)
Bonjour
Voici d'abord ce qu'il faudrait connaitre essentiellement lorsqu'on à décomposer un nombre en produit de facteurs premiers :
1)la liste des 25 nombres premiers de 0 à 100 ={2,3,5,7,11,13,17,19,23,29,31,37,41,...,97}
2)Les critères de divisibilité de 2,3,5,9,11 (les plus fréquents et les plus importants)
3)Pour savoir si le nombre donné n est déjà un nombre premier ,c'est de le diviser par tous les nombres premiers jusqu'à dépasser Vn .

Comme application ,traitant vos deux exemples :
a)Pour le nombre n=12321?
a-1)n divisible par 3 car somme de ses chiffres 1+2+3+2+1=9 multiple de 3 donc 12321=3*4107
a-2)4107pour la meme raison est divisible par 3 donc 4107=3*1369
soit donc 12312=3²*1369.Reste à savoir si 1369 est il premier ou pas?Pour cela ,appliquer 3) V1369=37,et par chance comme 37 est premier,on s’arrête làet on écrit que 1369=37².Finalement 12321=3²*37².
Le second exemple d'application ,dans un instant .A tout de suite .

---

Réponse : Problème sur facteurs premiers ? de wab51, postée le 27-02-2020 à 20:03:23 (S | E)
b)Pour le cas de 11579?
Bien sur,la méthode de chercher à essayer tous les diviseurs premiers de la liste des nombres 2 à 11579 serait évidemment insensée.On doit donc trouver une autre méthode permettant de répondre plus souplement à la question: 11579 est il premier?
Rappel:Pour déterminer si un nombre n ≥ 2 est premier ,on doit chercher un diviseur de n parmi les nombres premiers successifs {2,3,5,7,..}jusqu'à la valeur de la racine carrée de ce nombre Vn.
V11579 ≈ 107,6 .On prendra la partie entière 107.Or,107 est un nombre premier ,en conséquence le nbre 11579 n'admet aucun diviseur entre 107 et 11579 car les diviseurs d'un nombre n vont par pair dont l'un est compris entre 2 et Vn=107, et l'autre compris entre Vn=107 et n=11579. .Puisque n=11579 n'admet aucun diviseur parmi les nbres successifs jusqu'à V11579 c.a.d 107 ,c'est donc un nombre premier (11579 est un nombre premier.

---

Réponse : Problème sur facteurs premiers ? de airlibre, postée le 29-02-2020 à 17:39:21 (S | E)
Rebonjour Wab51,

Désolé pour la réponse un peu tardive.
Tout d'abord merci bien pour votre exposé très fournis !👍
Je l'ai imprimé afin de le relire tranquillement au besoin...

Je connais déjà les notions que vous m'indiquez dans la première partie de vos réponses concernant les critères de divisibilité.
Je possède également une liste des nombres premiers jusqu'à 49999 ! Mais je
crois qu'on doit pouvoir trouver des np, avant ou après ce chiffre, à l'aide d'un
programme .
Je connais bien la définition selon laquelle un nombre premier n'est
divisible que par 1 ou par lui-même ainsi que le processus pour
trouver les facteurs premiers qui composent un nombre entier non premier.

J'éprouve quelque difficulté a appréhender vos explication pour le dernier paragraphe, il me sera nécessaire
de le relire encore... et avec des pauses car je ne suis pas encore bien familiarisé avec le langage et caractères mathématiques !...

Je réitère ma question de façon que j'espère plus claire :
comment savoir quel est le diviseur de l'avant dernier quotient s'il sagit d'un nombre diviseur élevé.
Exemple : 472636 bon, j'arrive à trouver sans dificulté 2^2, il me reste un quotient/dividende 118159 à décomposer
et qui ne correspond pas à une puissance n x n..., contrairement à mon exemple précédent.
Comment vais-je trouver que le dernier diviseur de ce chiffre correspond à 173 (np) !!??
(j'ai évidemment composé cet exemple en faisant l'inverse, c'est à dire en partant de 683 x 173 x 2^2 )
Existe-t'il un algorithme qui me permette de trouver le plus petit diviseur de 118159 autre que 1 ?
Pourriez-vous me donner un exemple concret d'application si cet algorithme existe ?

Merci encore.

-------------------
Modifié par airlibre le 01-03-2020 09:29

---

Réponse : Problème sur facteurs premiers ? de wab51, postée le 01-03-2020 à 11:24:33 (S | E)
Bonjour airlibre
Bon,je vous ai bien lu.Pour moi,avec toutes les connaissances que vous aviez présentées ,je dirais que vous êtes bien équipé .Votre problème est intéressant mais sincèrement le voir avec le cas de nombre Grand ou encore de nombre Très Grand ,cela me dépasse .Je me retire pour laisser la place aux spécialistes et aux doués à ce sujet .Peut-être que nos chers amis puente et tiruxa ,sont plus performants ,ont dù certainement pris connaissance à travers votre poste ,ils vous diront plus à ce sujet.Je vous souhaite un vif savoir à ce que vous cherchiez savoir.Très bon weekend et pour une prochaine fois.Merci

---

Réponse : Problème sur facteurs premiers ? de tiruxa, postée le 01-03-2020 à 11:46:04 (S | E)
Bonjour,

Tout d'abord Wab51, je dirais que ta modestie t'honore mais je ne pense pas être très compétent sur l'algorithmique.

Effectivement j'a déjà fait ce type de programme, "savoir si n est premier" on en trouve des exemples sur internet.

En fait le programme fait exactement pareil qu'à la main sauf qu'au lieu de diviser par les nombres premiers on divise par les nmbres impairs (puisque tous les premiers sont impairs sauf 2 on aura bien exploré toutes les divisions par les facteurs premiers.
On s'arrête lorsque on trouve un reste nul ou si on atteint la racine carré de n, on obtient donc soit un facteur premier divisant n soit le fait que n est premier.

Ceci dit ce genre de programme a ses limites et pour les très très très ..... très grands nombres même les ordi les plus performants n'y arivent pas si bien que l'on s'en sert comme code secret (code RSA, on y donne la clef n mais pour décoder il faut décomposer n ce qui est supposé infaisable).

---

Réponse : Problème sur facteurs premiers ? de airlibre, postée le 01-03-2020 à 12:46:31 (S | E)
Merci Web51 pour vos encouragements et à la prochaine !...👍

Merci également Tiruxa, si je vous ai bien compris, ma question mène à une impasse pour des nombres plus grands
que deux chiffres !?...

---

Réponse : Problème sur facteurs premiers ? de airlibre, postée le 01-03-2020 à 13:23:10 (S | E)
Rebonjour les amis !

Je viens de trouver la solution à mon petit problème :

Lien internet


Cà fonctionne, je l'ai testé sur 118159 et j'ai bien 173 comme plus petit diviseur

autre que 1 et qu'il aurait-été hyper fastidieux à trouver !...

Ce lien peu peut-être servir à d'autres ?...

Encore à tous !!

---

[POSTER UNE NOUVELLE REPONSE] [Suivre ce sujet]

Cours gratuits > Forum > Forum maths