Python Débutant en Boucle (pour Trouver les nombres Premiers)

Je fait restructurer le programme ressemble à ceci:

for p in range(2, n+1):
    for i in range(2, p):
        if p % i == 0:
            break
    else:
        print p,
print 'Done'

C'est peut-être un plus idiomatique de la solution (à l'aide d'un for boucle au lieu d'un while de la boucle), et fonctionne parfaitement.

L'extérieur for boucle itère sur tous les nombres de 2 à n.

L'intérieur on itère pour tous les nombres de 2 à p. S'il atteint un nombre qui divise de manière égale p, puis il éclate de l'intérieur de la boucle.

La else bloc s'exécute chaque fois que la boucle for n'est pas rompu (impression des nombres premiers).

Ensuite, le programme imprime 'Done' fois celle-ci terminée.

Comme une note de côté, il vous suffit de parcourir les 2 à la racine carrée de p, puisque chaque facteur a une paire. Si vous n'obtenez pas un match il n'y aura pas d'autres facteurs après la racine carrée, et le nombre sera premier.

OriginalL'auteur Volatility

Cela devrait fonctionner et est un peu plus optimisé

import math
for i in range(2, 99):
  is_prime = True
  for j in range(2, int(math.sqrt(i)+1)):
    if i % j == 0:
      is_prime = False
  if is_prime:
    print(i)

OriginalL'auteur Adeel

vous n'avez pas re-démarrer le i boucle après, vous trouverez un non-premier

p = i = 2
while p <= n:
    i = 2
    while i < p:
        if p%i == 0:
            p += 1 
            i = 1
        i += 1

    print p,
    p += 1

print "Done"

Un while boucle s'exécute le corps, puis vérifie si la condition d'en haut est True, si c'est vrai, il ne le corps à nouveau. Un for boucle s'exécute le corps une fois pour chaque élément de l'itérateur.

OriginalL'auteur tacaswell

Nous allons faire un couple de plus d'améliorations.

1. Vous savez 2 est le seul nombre premier pair, de sorte que vous ajoutez 2 à votre liste et commencer à partir de 3 incrémentant le numéro de votre être vérifié par 2.
2. Une fois que vous êtes passé le point à mi-chemin (voir ci-dessus sqrt et * exemples), vous n'avez pas besoin de test pour un nombre premier.
3. Si vous utilisez une liste pour garder une trace des nombres premiers, tout ce que vous devez faire est de diviser par ceux des nombres premiers.

J'ai écrit mon code et chacun des éléments ci-dessus permettrait d'améliorer mon code temps d'exécution d'environ 500%.

prime_list=[2]
def is_prime(a_num):
    for i in prime_list:
        div, rem = divmod(a_num, i)
        if rem == 0:
            return False    
        elif div < i:
            break;

    prime_list.append(a_num)        
    return True    

OriginalL'auteur Omid

for i in range(2, p):
    if p%i == 0:
        p=p+1 
     print "%s" % p,
     p=p+1

Je vais dire à votre erreur,dans la ligne 3 vous êtes incrimenting p mais en fait ce qui vous manque est votre je si votre je dans le cas précédent est disons 13 alors il va vérifier votre boucle après le 13, mais c'est en laissant 2,3,5,7,11 de sorte que son une erreur .c'est ce qui se passe dans le cas de 27 votre-je avant 27 13 et maintenant, il va vérifier à partir de 14.et je ne pense pas u besoin d'une solution.

OriginalL'auteur mayank

Voici un plus vaste exemple avec l'optimisation dans l'esprit de Python 3.

import sys

inner_loop_iterations: int = 0

def is_prime(n):
    a: int = 2
    global inner_loop_iterations

    if n == 1:
        return("Not prime")
    elif n == 2:
        return("Prime")

    while a * a <= n + 1:
        inner_loop_iterations += 1
        # This if statement reduces the number of inner loop iterations by roughy 50%
        # just weeding out the even numbers.
        if a % 2 == 0:
            a += 1
        else:
            a += 2

        if n % 2 == 0 or n % a == 0:
            return ("Not prime")
    else:
        return ("Prime")

while True:
    sys.stdout.write("Enter number to see if it's prime ('q' to quit): ")
    n = input()
    if not n:
        continue
    if n == 'q':
        break

    try:
        n = int(n)
    except ValueError:
        print("Please enter a valid number")

    if n < 1:
        print("Please enter a valid number")
        continue

    sys.stdout.write("{}\n".format(is_prime(n)))
    sys.stderr.write("Inner loops: {}\n\n".format(inner_loop_iterations))
    inner_loop_iterations=0

Ce programme a deux principales optimisations, première itération porte uniquement à partir de la 2 à la racine carrée de n et il ne parcourt les nombres impairs. L'utilisation de ces optimisations, j'ai pu constater que le nombre 1000000007 est le premier que dans 15811 itérations de boucle.

OriginalL'auteur Sonny Parlin

Ce qui à mon avis est un plus, de façon à optimiser. Trouve tous les nombres premiers jusqu'à 1 000 000 en moins de 8 secondes sur mon installation.

Il est également l'un de mes tout premiers essais de python, donc je me tiens à être corrigé

class prime:
    def finder (self):
        import math
        n = long(raw_input("What number should I go up to? "))
        for i in range(2, n):
            is_prime = True
            if i % 2 == 0:
                is_prime = False
            for j in range(3, long(math.sqrt(i) + 1), 2):
                if i % j == 0:
                    is_prime = False
                    break
            if is_prime:
                print(i)


prime().finder()

OriginalL'auteur J. Fenech