Calculer tous les facteurs possibles d'un nombre premier

Question

Était en cours d'un didacticiel Python et est tombé sur un exemple pour vérifier si un nombre est premier ou non. J'ai changé quelques choses afin que le résultat afficherait une liste de tous les facteurs possibles du nombre, si le nombre n'est pas un premier, Cependant, le code n'a pas fonctionné.

code:

def isprime(number): 
    print "Reticulating Splines..." 
    fnum=[1,] 
    notprime=0 
    for p in range(2, number): 
     if (number % p) == 0: 
      notprime=1 
      fnum.append(p) 
      continue 
     if notprime == 1:  
      return number, "is not a prime because of these factors", fnum 
     else: 
      return True 
num =int(raw_input("Enter number: ")) 
print isprime(num) 

Sortie:

Enter number: 12 
Reticulating Splines... 
(12, 'is not a prime because of these factors', [1, 2, 3, 4]) 
>>> 
Enter number: 25 
Reticulating Splines... 
(25, 'is a prime number') 

Résultats escomptés:

Enter number: 12 
Reticulating Splines... 
(12, 'is not a prime because of these factors', [1, 2, 3, 4, 6]) 

Enter number: 25 
Reticulating Splines... 
(25, 'is not a prime because of these factors', [1,5]) 

structure de contrôle est mauvaise à mon avis, mais quelqu'un peut-il réparer mon code?

Je comprends comment fonctionne range(): Dans ce cas range() est donné un début et une valeur d'arrêt, étape par défaut à 1. Je comprends que continuer, continue une boucle, mais puis-je l'utiliser? Je pense que c'est faux.

MISE À JOUR
résolu, problème avec indentation la continuer aurait dû être la boucle, idem pour le si ... notprime.

def isprime(number): 
    print "Reticulating Splines..." 
    fnum=[1,] 
    notprime=0 
    for p in range(2, number): 
     if (number % p) == 0: 
      notprime=1 
      fnum.append(p) 
    if notprime == 1:  
     return number, "is not a prime because of these factors", fnum 
    else: 
     return number, "is a prime number" 
num =int(raw_input("Enter number: ")) 
print isprime(num) 

Update2: (Thx à @neil)
Et le continue est simplement stupide

code mis à jour et les comparaisons entre vitesse n/2 et sqrt (n) Merci à @neil et @emmanuel
n/2 code: v2

import time 
def isprime(number): 
    start=time.clock() 
    print "Reticulating Splines..." 
    fnum=[1,] 
    notprime=0 
    for p in range(2, (number/2)+1): 
     if (number % p) == 0: 
      notprime=1 
      fnum.append(p) 
    end=time.clock() 
    if notprime == 1:  
     return number, "is not a prime because of these factors", fnum, "Time taken", end-start 
    else: 
     return number, "is a prime number. Time Taken", end-start 
print "Prime or factor calculator v2 using n/2" 
print # 
num =int(raw_input("Enter number: ")) 
print isprime(num) 

sqrt (n) Code: v3

import math, time 
def isprime(number): 
    start=time.clock() 
    print "Reticulating Splines..." 
    fnum = [1,] 
    last = int(math.ceil(math.sqrt(number))) 
    for p in range(2, last + 1): 
     if (number % p) == 0: 
      fnum.append(p) 
      fnum.append(number/p) 
    # Remove duplicates, sort list 
    fnum = list(set(fnum)) 
    fnum.sort() 
    end=time.clock() 
    if len(fnum) > 1:  
     return number, "is not a prime because of these factors", fnum ,"Time taken", end-start 
    else: 
     return True, "Time taken", end-start 

print "Prime or factor calculator v3 using sqrt(n)" 
print # 

num =int(raw_input("Enter number: ")) 

print isprime(num) 

sortie (affichage temps seulement)

de temps pour sqrt (n) Code: v3
premier ou d'une calculatrice de facteur v3 à l'aide sqrt (n)
Saisissez le numéro: 999999
Temps pris ', 0.0022617399697466567

temps pour le code n/2: v2
premier ou calcul de facteur v2 utilisant n/2
Entrer le numéro: 999999
Temps pris: 0.11294955085074321

temps pour le code original (n): v1
Prime ou calculatrice facteur v1
Entrer le numéro: 999999
Temps pris: 0,22059172324972565

v1 et v2 ne pouvait pas gérer les numéros 999999999 , 999999999999 et 999999999999999, les deux ont donné MemoryError

Cependant v 3 les trois numéros traitées:
999999999: 0,010536255306192288
999999999999: 0,75631930873896636
999999999999999: 24,04511104064909

La coque pour 9999999999999999 et accroche donne un MemoryError pour 999999999999999999

Merci à @Lennart, je pense à la réécriture le code d'une manière plus conviviale OOP, en utilisant des classes. Mais je ne semble pas le faire correctement.

Answer 1

Le problème est votre indentation - if notprime==1: ne doit pas être dans la boucle. Il devrait seulement avoir un niveau d'indentation. En outre, continue est inutile.

EDIT:

Une amélioration que vous pouvez faire (je viens de travailler sur les nombres premiers hier soir pour un problème d'Euler Project) est en boucle uniquement à n/2 - il ne peut pas être un facteur supérieur à la moitié de la nombre.

Answer 2

Votre if notprime ... final et les trois lignes qui le suivent sont indentés trop loin et sont donc exécutés à l'intérieur de la boucle, plutôt qu'à l'extérieur.

Answer 3

Vous revenez après avoir testé un seul numéro. Déplacez les tests if et les retours à l'extérieur de la boucle for.

De même, renvoyer True s'il s'agit d'un nombre premier, et une chaîne si ce n'est pas n'est pas pratique. Si vous appelez alors

if isprime(7): 

Ce sera toujours évaluer aussi vrai. Je me suis amélioré les choses un peu:

def factors(number): 
    fnum=[] 
    for p in range(2, number): 
     if (number % p) == 0: 
      fnum.append(p) 
    return fnum 

for x in range(100): 
    f = factors(x) 
    if f: 
     print x, "is not a prime and has factors", f 
    else: 
     print x, "is a prime" 

Answer 4

@neil:

« Une amélioration que vous pouvez faire ... est en boucle uniquement à n/2 - il ne peut pas être un facteur supérieur à la moitié du nombre. »

Par ailleurs, la valeur la plus élevée que vous devez tester est int(math.ceil(math.sqrt(n))), pas besoin d'aller à n/2 si chaque fois que vous obtenez une valeur, vous obtenez une (associée à savoirsi a x b = n, que ce soit a ou b est inférieure à la racine carrée de n et l'autre est plus):

def isprime(number): 
    print "Reticulating Splines..." 
    fnum = [1,] 
    last = int(math.ceil(math.sqrt(number))) 
    for p in range(2, last + 1): 
     if (number % p) == 0: 
      fnum.append(p) 
      fnum.append(number/p) 
    # Remove duplicates, sort list 
    fnum = list(set(fnum)) 
    fnum.sort() 
    if len(fnum) > 1:  
     return number, "is not a prime because of these factors", fnum 
    else: 
     return True 

Des performances supérieures, même si à la fin de la liste ne sont pas triées (mais cela peut être fait à l'intérieur la boucle en ajoutant les 2 chiffres p et number/p aux bons index).