Décomposition en produit de facteurs premiers
dans Arithmétique
Bonjour à tou.te.s
Comme beaucoup de personnes, je m'intéresse (en amateur) aux nombres et en particulier à leur décomposition.
J'aimerais avoir votre avis sur ce qui suit.
- Si je prends un nombre comme 69 646 103 (qui est le produit de 7 013 par 9 931), je sais qu'il y a 902 nombres premiers compris entre 1 et 7 013, et donc 902 tests à faire pour trouver que 7 013 est un des deux facteurs.
- J'ai trouvé une "méthode" qui en 126 tests me permet de trouver 7 013 (pour ce nombre donné)
- Savez-vous si cette "méthode" que j'utilise existe déjà ou existe-t-il des méthodes existantes plus rapides ?
Merci d'avance
Comme beaucoup de personnes, je m'intéresse (en amateur) aux nombres et en particulier à leur décomposition.
J'aimerais avoir votre avis sur ce qui suit.
- Si je prends un nombre comme 69 646 103 (qui est le produit de 7 013 par 9 931), je sais qu'il y a 902 nombres premiers compris entre 1 et 7 013, et donc 902 tests à faire pour trouver que 7 013 est un des deux facteurs.
- J'ai trouvé une "méthode" qui en 126 tests me permet de trouver 7 013 (pour ce nombre donné)
- Savez-vous si cette "méthode" que j'utilise existe déjà ou existe-t-il des méthodes existantes plus rapides ?
Merci d'avance
Réponses
-
Bonjour,
Si $7013$ n'est pas premier, alors il existe $a$ et $b$ avec $a \leq b$ tels que $ab=7013 \geq a^2$ et donc $a \leq \sqrt{7013} <84$ on a donc $84$ tests au faire (au maximum). Et comme ni $a$ ni $b$ ne sont pairs car $7013$ est impair, alors on a $42$ tests à faire (au maximum)... -
@YvesM : Tu parles de tester si $7013$ est premier ?
J'ai une méthode pour factoriser tout nombre naturel $n$ en facteurs premiers et qui fait UN SEUL test pour 69 646 103 :
1. Si $n=69646103$, retourner $7013 \times 9931$.
2. Sinon, appliquer un algorithme quelconque de décomposition en facteurs premiers.
Il existe donc des méthodes plus rapides. -
Désolé, je me suis mal exprimé.
Si je vous demande de décomposer 69 646 103 en produit de facteurs premiers, quelle est, d'après vous, la méthode la plus rapide et surtout combien d'itérations vous faut-il pour trouver un des deux facteurs.
En ce qui me concerne, il me faut 126 itérations pour trouver le facteur le plus petit. -
Sans te décourager , il existe des algorithmes de factorisation d'un entier n < nombre n de 100 chiffres...
Que donne ta méthode pour n = 123926186396330317
temps de factorisation ;Time elapsed: 0d 0h 0m 0.0s -
Paskalprevo:
Ton algorithme fonctionne-t-il pour d'autres nombres? -
@ LEG
Je n'ai pas testé de nombre aussi grand parce que, pour l'instant, ce qui m'intéresse c'est uniquement le nombre d'itérations que je dois effectuer pour arriver à trouver deux facteurs (qui peuvent être premiers ou composés). Mais je vais tâcher de créer un programme en python pour te répondre.
@LEG, @Fin de partie
Ma méthode ou plutôt mes méthodes ne fonctionnent pas efficacement pour tous les nombres. Il y a certains nombres, quelque soient leurs tailles, dont je peux trouver deux facteurs (premiers ou composés) en 1, 2, 3 ou plus d'itérations mais (beaucoup) d'autres nécessitent une autre approche.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 6
+1 Invité