Un programme de prime factoriser un nombre donné

Question

n = 600851475143 
i = 2 

while i * i < n: 
    while n%i == 0: 
     n = n/i 
    i = i + 1 

print (n) 

Ceci est un programme en python qui trouve le plus grand facteur premier d'un nombre donné. Je me demandais s'il y avait moyen de le modifier pour qu'on puisse trouver tous les facteurs premiers au lieu de simplement le plus grand. Je pensais que ce programme étant rapide et soigné, y a-t-il un moyen d'ajouter quelques lignes de code qui le modifient en ce dont j'ai besoin, quels sont les principaux facteurs?

Answer 1

Voici un programme simple pour tenir compte des entiers:

Python 2.7.5+ (default, Sep 17 2013, 15:31:50) 
[GCC 4.8.1] on linux2 
Type "help", "copyright", "credits" or "license" for more information. 
>>> def factors(n): 
...  f, fs = 2, [] 
...  while f * f <= n: 
...   if n % f == 0: 
...    fs.append(f) 
...    n = n/f 
...   else: 
...    f = f + 1 
...  fs.append(n) 
...  return fs 
... 
>>> factors(600851475143) 
[71, 839, 1471, 6857] 

Il y a de meilleures façons de factoriser des entiers, mais c'est assez pour vous aider à démarrer. Si vous êtes intéressé par la programmation avec des nombres premiers, je recommande modestement this essay sur mon blog.