Factorisation en nombres premiers
Un article de Wikipedia.
(Différences entre les versions)
(→Résultat) |
(→Conclusions) |
||
| (Une révision intermédiaire masquée) | |||
| Ligne 12 : | Ligne 12 : | ||
La méthode utilisée consiste à tenter de diviser l'entier à factoriser ''n'' par les nombres premiers ''p'' inférieurs à √''n''. | La méthode utilisée consiste à tenter de diviser l'entier à factoriser ''n'' par les nombres premiers ''p'' inférieurs à √''n''. | ||
| - | Si un nombre premier ''p'' divise ''n''. La procédure est répétée sur ''k=n/p'' en recherchant les nombres premiers ''p''' qui divise ''k'' pour √''k>=p'>=p''. | + | Si un nombre premier ''p'' divise ''n''. La procédure est répétée sur ''k = n/p'' en recherchant les nombres premiers ''p''' qui divise ''k'' pour √''k >= p' >= p''. |
== Résultat == | == Résultat == | ||
| Ligne 24 : | Ligne 24 : | ||
== Conclusions == | == Conclusions == | ||
| + | * En utilisant des entiers non signés, il est possible de factoriser des nombres deux fois plus élevés. | ||
| + | * L'affichage de la factorisation d'un nombre devrait regrouper les nombres premiers et les présenter sous forme ''p^(m)'' au lieu de ''p,p,p'',.. si ''m > 1''. | ||
| + | |||
== Ressources == | == Ressources == | ||
* Factorisation en nombres premier [[Media:Premier_pas.PDB]] | * Factorisation en nombres premier [[Media:Premier_pas.PDB]] | ||
Version actuelle
Sommaire |
Factorisation en nombres premiers
But
Factoriser un entier en produits de nombres premiers.
Introduction
- Un nombre premier est un nombre entier divisible uniquement par 1 et par lui-même comme pour 2,3,37 et 1039.
- Tout nombre entier peut être factorisé de manière unique sous la forme de produits de nombres premiers.
- Algorithme
La méthode utilisée consiste à tenter de diviser l'entier à factoriser n par les nombres premiers p inférieurs à √n.
Si un nombre premier p divise n. La procédure est répétée sur k = n/p en recherchant les nombres premiers p' qui divise k pour √k >= p' >= p.
Résultat
L'implémentation est donnés dans les ressouces (voir Ressources).
Une liste contient l'ensemble des nombres premiers utilisés durant la procédure de factorisation.
Une autre liste contient les nombres premiers de la factorisation du nombre à factoriser.
La factorisation se base sur des nombres entiers et est donc limité à des nombres n <= 2^31-1 = 2'147'483'647.
Conclusions
- En utilisant des entiers non signés, il est possible de factoriser des nombres deux fois plus élevés.
- L'affichage de la factorisation d'un nombre devrait regrouper les nombres premiers et les présenter sous forme p^(m) au lieu de p,p,p,.. si m > 1.
Ressources
- Factorisation en nombres premier Media:Premier_pas.PDB
- Source Premier.pas
Catégories: Logiciel | Pascal | Palm
