Utiliser Python calculer le nombre premier 1000

Question

J'essaie de trouver le nombre premier 1000 et j'essaie de le faire sans tricher la mémorisation ou un autre code. Pouvez-vous s'il vous plaît me dire si je suis sur la bonne voie avec mon code ou complètement hors de la base?

primes = [] 
num = 3 
while (len(primes)) < 1000: 
    if num/2 == 0: 
     num = num + 1 
    else: 
     x = num - 1 
     for z in range(2,x): 
      if num % z == 0 : 
       num = num + 1 
      else: 
       primes.append(num) 
       num = num + 1 

print primes[1000] 

Answer 1

Vous avez quelques problèmes (num/2 == 0 devrait être num % 2 == 0) , mais vraiment, en utilisant continue et break pourrait vraiment aider. par exemple.

for z in range(2,x): # xrange would be a performance win on python2.x 
    if num % z == 0 : 
     num = num + 1 
    else: 
     primes.append(num) 
     num = num + 1 

Dans cette boucle, vous pourriez vous retrouver incrémenter num tout un tas de fois. en réalité, vous ne voulez l'incrémenter qu'une seule fois (pour passer au numéro suivant). Donc, ici, vous voulez break après l'avoir incrémenté. En outre, la déclaration else devrait être sur la boucle for:

for z in range(2, x): 
    if num % z == 0: 
     break # exit the for loop, don't execute `else` clause. 
else: 
    # only executes if `break` was never encountered. 
    primes.append(num) 

# This happens no matter what and should only happen once 
# Might as well pull it out of the loop. 
num += 1 

---

<sup>la vérification de la divisibilité par 2 est en quelque sorte inutile ici - Il est la première itération de la boucle. Si vous avez utilisé xrange (pour python2.x) et break comme je l'ai décrit, cette optimisation (probablement) ne vaut pas la peine.

En plus: Vous n'avez pas vraiment besoin d'exécuter la boucle 2-N - 1, vous pouvez réellement sortir avec courir la boucle de 2 à int(math.sqrt(N)) ce qui en fait beaucoup :-) plus efficace, bien que toujours pas le meilleur vous pouvez faire ... Le Sieve of Eratosthenes est un autre algorithme pour le faire plus efficacement et il y a probablement de meilleures méthodes que cela (même si je ne suis pas un expert dans ce domaine)</sup>