Factoriser un entier en produit de deux nombres premiers
AFmika
Messages postés
25
Date d'inscription
mardi 14 juillet 2015
Statut
Membre
Dernière intervention
24 juin 2016
-
6 oct. 2015 à 13:22
AFmika Messages postés 25 Date d'inscription mardi 14 juillet 2015 Statut Membre Dernière intervention 24 juin 2016 - 3 janv. 2016 à 16:50
AFmika Messages postés 25 Date d'inscription mardi 14 juillet 2015 Statut Membre Dernière intervention 24 juin 2016 - 3 janv. 2016 à 16:50
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/101196-factoriser-un-entier-en-produit-de-deux-nombres-premiers
https://codes-sources.commentcamarche.net/source/101196-factoriser-un-entier-en-produit-de-deux-nombres-premiers
3 janv. 2016 à 16:50
Mon algorithme fait un peu pres la meme chose sauf qu'ici il n'y a pas de lieu de calcul quantique.
Pas mathematique dites vous? ce n'est pas du random pur comme vous le pretendez mais du random purement probabiliste d'ailleur la frequence de generation des bons nombres est le principal atout de l'algorithme de Shor ce qui le rend 'magique' entre autre car les nombres sont souvent adequats et repondent aux nombres attendus .
11 oct. 2015 à 17:01
Le programme factor1.exe de Thomas R. Nicely met 6 milisecondes pour factoriser
2^150 + 1 = 1427247692705959881058285969449495136382746625 en :
5*5*5*13*41*61*101*1201*1321*8101*63901*268501*13334701*1182468601
et il permet d'aller bien plus loin. C'est pour cela qu'il est intéressant de le signaler.
11 oct. 2015 à 14:54
Cependant, il me semble plus judicieux que tu postes un snippet avec ton code
11 oct. 2015 à 11:24
Tu fais une recherche mathématique que tu dis être "polynomiale" alors que ton algorithme se base sur un random, c'est absurde ! Quand je reprends ton exemple 6 = 2*3 et que cela me renvoie une erreur, je ne peux pas te donner plus que 1/5 à l'évaluation du code...
Un petit conseil pour améliorer ta manière de programmer : ne mélange pas calcul et présentation, si tu fais un algorithme mathématique le résultat doit être un objet mathématique (dans ton cas, la liste des facteurs premiers), pas une modification de la page, il ne faut pas tout mélanger.
Sinon pour ceux que ça intéresserait, voici un algorithme linéaire pour faire un vrai calcul de décomposition en facteur premiers qui fonctionne dans tous les cas.
<html> <head> <script> function primeFactorization(n) { if (isNaN(n) || n == 0) return []; if (n < 0) n = -n; var result = []; for (i = 2; i <= n;) { if (n % i == 0) { result.push(i); n /= i; } else { i++; } } return result; } </script> </head> <body> Nombre entier :<br/> <input type="text" id="n" maxlength="7" onkeyup="document.getElementById('r').value = primeFactorization(document.getElementById('n').value)"/> <br/> Décomposition :<br/> <input type="text" id="r" disabled/> </body> </html>Attention : pour les très grands nombre premiers, le calcul peut prendre du temps. J'ai donc limité la taille de l'input à 7 caractères, le calcul le plus long sera celui de n=9999991, qui répond en temps correct.
11 oct. 2015 à 08:58
6 oct. 2015 à 19:47
Je signale : http://www.trnicely.net/ où il y a le fichier factor1.zip qui contient le source en langage C et l'exécutable d'un bon logiciel pour factoriser des entiers avec des performances très correctes.
6 oct. 2015 à 19:10
6 oct. 2015 à 13:30