Imprimer une série de nombres premiers en python

Je suis en train d'apprendre de programmation Python, et je suis assez nouveau à ce.

J'ai eu des problèmes à l'impression d'une série de nombres premiers de un à cent. Je ne peux pas déterminer quel est le problème avec mon code.

Voici ce que j'ai écrit; il imprime tous les nombres impairs au lieu de nombres premiers:

for num in range(1,101):
    for i in range(2,num):
        if (num%i==0):
            break
        else:
            print(num)
            break

source d'informationauteur user1546721 | 2012-07-23

39

Vous avez besoin de vérifier tous les nombres de 2 à n-1 (à sqrt(n) en fait, mais bon, que ce soit n).
Si n est divisible par aucun des nombres, il n'est pas premier. Si un nombre est premier, l'imprimer.
```
for num in range(2,101):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print num
```
Vous pouvez écrire la même beaucoup plus court et plus pythonic:
```
for num in range(2,101):
    if all(num%i!=0 for i in range(2,num)):
       print num
```
Comme je l'ai déjà dit, il serait préférable de vérifier les diviseurs pas de 2 à n-1, mais à partir de 2 à sqrt(n):
```
import math
for num in range(2,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num
```
Pour les petits nombres comme 101 il n'a pas d'importance, mais pour 10**8 la différence sera vraiment gros.

Vous pouvez l'améliorer un peu plus par incrémentation de la plage vous de vérifier par 2, et donc la seule vérification des numéros impairs. Comme:
```
import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num
```
Édité:

Comme dans la première boucle, les nombres impairs sont sélectionnés, dans la seconde boucle pas
besoin de vérifier avec le même nombre, donc " je " valeur peut être commencer par 3 et
sautée par 2.
```
import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
        print num
```

break termine la boucle qu'il est actuellement. Donc, vous n'êtes jamais vérifier si il divisible par 2, vous donnant tous les nombres impairs.

for num in range(2,101):
    for i in range(2,num):
        if (num%i==0):
            break
    else:
        print(num)

cela étant dit, il ya beaucoup de meilleures façons de trouver des nombres premiers en python que cela.

for num in range(2,101):
    if is_prime(num):
        print(num)

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

8

Au lieu de la division de première instance, une meilleure approche, inventé par le mathématicien grec Eratosthène plus de deux mille ans, est à tamis à plusieurs reprises par le rejet des multiples de nombres premiers.

Commencez par faire une liste de tous les nombres de 2 au maximum désiré le premier n. Puis plusieurs reprises de prendre la plus petite décroise nombre et de la croix de l'ensemble de ses multiples; le nombre qui restent non barrés sont de qualité.

Par exemple, considérons les nombres inférieurs à 30. Initialement, 2 est identifié comme le premier, puis 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 et 30 sont croisés. 3 est identifié comme le premier, puis 6, 9, 12, 15, 18, 21, 24, 27 et 30 sont croisés. Le prochain premier est de 5, 10, 15, 20, 25 et 30 sont croisés. Et ainsi de suite. Le nombre qui restent sont le premier: 2, 3, 5, 7, 11, 13, 17, 19, 23, et 29.
```
def primes(n):
  sieve = [True] * (n+1)
  for p in range(2, n+1):
    if (sieve[p]):
      print p
      for i in range(p, n+1, p):
        sieve[i] = False
```
Une version optimisée du tamis poignées 2 séparément et cribles seulement des nombres impairs. Aussi, puisque tous les composites de moins que la place de l'actuel premier sont traversés par de plus petits nombres premiers, la boucle interne peut commencer à p^2 au lieu de p et de la boucle externe peut s'arrêter à la racine carrée de n. Je vais laisser la version optimisée pour vous de travailler sur.
3

Je suis un promoteur de ne pas en supposant que la meilleure solution et de le tester. Ci-dessous sont quelques modifications que j'ai fait pour créer des classes d'exemples par les deux @igor-chubin et @user448810. Tout d'abord permettez-moi de dire que toutes les bonnes informations, merci les gars. Mais je dois reconnaître @user448810 pour sa solution intelligente, qui s'avère être le plus rapide, et de loin (de ceux que j'ai testé). Donc, bravo à vous, monsieur! Dans tous les exemples que j'ai utiliser une valeur de 1 million (1.000.000) de n.

N'hésitez pas à essayer le code.

Bonne chance!

Méthode 1 comme décrit par Igor Chubin:
```
def primes_method1(n):
    out = list()
    for num in range(1, n+1):
        prime = True
        for i in range(2, num):
            if (num % i == 0):
                prime = False
        if prime:
            out.append(num)
    return out
```
Référence: 272+ secondes

Méthode 2 comme décrit par Igor Chubin:
```
def primes_method2(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, num)):
            out.append(num)
    return out
```
Référence: 73.3420000076 secondes

Méthode 3 comme décrit par Igor Chubin:
```
def primes_method3(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out
```
Référence: 11.3580000401 secondes

Méthode 4 comme décrit par Igor Chubin:
```
def primes_method4(n):
    out = list()
    out.append(2)
    for num in range(3, n+1, 2):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out
```
Référence: 8.7009999752 secondes

Méthode 5 comme décrit par user448810 (j'ai pensé que c'était très habile):
```
def primes_method5(n):
    out = list()
    sieve = [True] * (n+1)
    for p in range(2, n+1):
        if (sieve[p]):
            out.append(p)
            for i in range(p, n+1, p):
                sieve[i] = False
    return out
```
Référence: 1.12000012398 secondes

Notes: Solution 5 énumérées ci-dessus (comme proposé par user448810) s'est avéré pour être le plus rapide et honnêtement calme, créative et intelligente. Je l'aime. Merci les gars!!

EDIT: Oh, et par la manière, je n'ai pas le sentiment qu'il était nécessaire d'importer la bibliothèque de mathématiques pour la racine carrée d'une valeur équivalente est juste (n**.5). Sinon, je n'ai pas modifier beaucoup d'autres ensuite rendre les valeurs sont enregistrées dans le et le tableau de sortie renvoyée par la classe. Aussi, il serait probablement un peu plus efficace pour stocker les résultats dans un fichier que verbeux et pourrait sauver beaucoup de mémoire, si c'était juste un à la fois, mais en coûterait un peu plus de temps en raison d'écritures sur le disque. Je pense qu'il y a toujours de la place pour l'amélioration, même si. J'espère donc que le code de sens que les gars.

La meilleure façon de résoudre le problème ci-dessus serait d'utiliser le "Miller Rabin Test de Primalité" de l'algorithme. Il utilise une approche probabiliste pour déterminer si un nombre est premier ou pas. Et c'est par loin le plus efficace algorithme que j'ai rencontré pour la même chose.

Le python de la mise en œuvre de la même est démontré ci-dessous:

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in xrange(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in xrange(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

Un Programme en Python module de fonction qui renvoie la 1 st N nombres premiers:

def get_primes(count):
    """
        Return the 1st count prime integers.
    """
    result = []
    x=2
    while len(result) in range(count):
        i=2
        flag=0
        for i in range(2,x):
            if x%i == 0:
                flag+=1
                break
            i=i+1
        if flag == 0:
            result.append(x)
        x+=1
    pass
    return result

1

Ma façon de liste de nombres premiers d'un numéro d'entrée sans trop de tracas est à l'aide de la propriété que vous pouvez obtenir tout nombre qui n'est pas premier avec la somme des nombres premiers.

Donc, si vous divisez le numéro de l'entrée avec tous les nombres premiers inférieurs, et il n'est pas divisible par l'un d'eux, vous savez que vous avez un nombre premier.

Bien sûr, il ya toujours des façons plus rapides d'obtenir les nombres premiers, mais celui-ci exécute déjà très bien, surtout parce que vous n'êtes pas divisant le numéro de l'entrée par un nombre quelconque, mais seulement les nombres premiers de tous la voie à ce nombre.

Avec ce code, j'ai réussi sur mon ordinateur à la liste de tous les nombres premiers jusqu'à 100 000 en moins de 4 secondes.
```
import time as t

start = t.clock()

primes = [2,3,5,7]

for num in xrange(3,100000,2):
    if all(num%x != 0 for x in primes):
        primes.append(num)

print primes
print t.clock() - start
print sum(primes)
```

Impression de n nombres premiers à l'aide de python:

num = input('get the value:')
for i in range(2,num+1):
    count = 0
    for j in range(2,i):
        if i%j != 0:
            count += 1
    if count == i-2:
        print i,

0

Igor Chubin's réponse peut être améliorée. Lors de l'essai si X est premier, l'algorithme ne pas avoir à vérifier chaque numéro jusqu'à la racine carrée de X, il n'a qu'à vérifier les nombres premiers jusqu'à la sqrt(X). Ainsi, il peut être plus efficace si elle se réfère à la liste des nombres premiers qu'il crée. La fonction ci-dessous renvoie une liste de tous les nombres premiers dans le groupe b, ce qui est pratique comme une liste pour plusieurs raisons (par exemple, lorsque vous voulez savoir le nombre de nombres premiers < b). Par la seule vérification que les premiers, il permet de gagner du temps au plus grand nombre (à comparer à environ 10 000; la différence est frappante).
```
from math import sqrt
def lp(b)
    primes = [2]
    for c in range(3,b):
        e = round(sqrt(c)) + 1
        for d in primes:
            if d <= e and c%d == 0:
                break
        else:
            primes.extend([c])
    return primes
```
0

Voici un moyen simple et intuitif de la version de vérifier si c'est un premier dans une fonction RÉCURSIVE! 🙂 (Je l'ai fait comme un devoir à la maison pour un MIT de la classe)
En python, il fonctionne très rapidement jusqu'en 1900. SI vous essayez plus de 1900, vous aurez une intéressante erreur 🙂 (u, comme pour vérifier combien de numéros de votre ordinateur peut gérer?)
```
def is_prime(n, div=2):

    if div> n/2.0: return True

    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)

#The program:
until = 1000
for i in range(until):
    if is_prime(i):
        print i
```
Bien sûr... si vous aimez les fonctions récursives, ce petit code peut être mis à niveau avec un dictionnaire d'augmenter considérablement ses performances, et d'éviter que l'erreur drôle.
Voici un simple Niveau 1 mise à niveau avec une MÉMOIRE de l'intégration:
```
import datetime
def is_prime(n, div=2):
    global primelist
    if div> n/2.0: return True
    if div < primelist[0]:
        div = primelist[0]
        for x in primelist:
            if x ==0 or x==1: continue
            if n % x == 0:
                return False
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
    if is_prime(i):
        primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."

finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"
```
Voici le resultat, où j'ai imprimé sur les 100 derniers nombres premiers trouvés.

heure et la date: 2013-10-15 13:32:11.674448

Il y a 9594 nombres premiers, jusqu'à 100000

[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719, 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99487, 99469, 99439, 99431, 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99149, 99139, 99137, 99133, 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 98929, 98927, 98911, 98909, 98899, 98897] ...

A pris à votre ordinateur 0:00:40.871083 pour calculer

De sorte qu'Il a fallu 40 secondes pour mon ordinateur portable i7 de la calculer. 🙂

def prime_number(a):
    yes=[]
    for i in range (2,100):
        if (i==2 or i==3 or i==5 or i==7) or (i%2!=0 and i%3!=0 and i%5!=0 and i%7!=0 and i%(i**(float(0.5)))!=0):
            yes=yes+[i]
    print (yes)

# computes first n prime numbers
def primes(n=1):
    from math import sqrt
    count = 1
    plist = [2]
    c = 3
    if n <= 0 :
        return "Error : integer n not >= 0"
    while (count <= n - 1):    # n - 1 since 2 is already in plist
        pivot = int(sqrt(c))
        for i in plist:
            if i > pivot :    # check for primae factors 'till sqrt c
                count+= 1
                plist.append(c)
                break
            elif c % i == 0 :
                break    # not prime, no need to iterate anymore
            else :
                continue 
        c += 2    # skipping even numbers              
    return plist

min=int(input("min:"))
max=int(input("max:"))
for num in range(min,max):
    for x in range(2,num):
        if(num%x==0 and num!=1):
            break
        else:
            print(num,"is prime")
            break

0

Vous êtes à la terminaison de la boucle trop tôt. Après avoir testé toutes les possibilités dans le corps de la boucle for, et de ne pas briser, alors le nombre est premier. Comme on n'est pas premier, il faut commencer par 2:
```
for num in xrange(2, 101):
    for i in range(2,num):
        if not num % i:
            break
    else:
        print num
```
Dans une solution plus rapide vous essayez seulement de diviser par des nombres premiers qui sont plus petits ou égaux à la racine du nombre que vous testez. Ceci peut être réalisé en se souvenant de tous les nombres premiers vous avez déjà trouvé. En outre, vous n'avez qu'à tester nombres impairs (sauf 2). Vous pouvez mettre de l'algorithme qui en résulte dans un générateur de sorte que vous pouvez l'utiliser pour stocker des nombres premiers dans un conteneur ou tout simplement de les imprimer:
```
def primes(limit):
    if limit > 1:
        primes_found = [(2, 4)]
        yield 2
        for n in xrange(3, limit + 1, 2):
            for p, ps in primes_found:
                if ps > n:
                    primes_found.append((n, n * n))
                    yield n
                    break
                else:
                    if not n % p:
                        break

for i in primes(101):
    print i
```
Comme vous pouvez le voir il n'est pas nécessaire de calculer la racine carrée, il est plus rapide de magasin de la place pour chaque nombre premier et comparer chaque diviseur de ce nombre.

Ceci est un exemple de programme que j'ai écrit pour vérifier si un nombre est premier ou pas.

def is_prime(x):
    y=0
    if x<=1:
        return False
    elif x == 2:
        return True
    elif x%2==0:
        return False
    else:
        root = int(x**.5)+2
        for i in xrange (2,root):
            if x%i==0:
                return False
                y=1
        if y==0:
            return True

n = int(raw_input('Enter the integer range to find prime no :'))
p = 2
while p<n:
  i = p
  cnt = 0
  while i>1:
    if p%i == 0:
        cnt+=1
    i-=1
  if cnt == 1:
     print "%s is Prime Number"%p
  else:
     print "%s is Not Prime Number"%p
  p+=1

À l'aide de la fonction filtre.

l=range(1,101)
for i in range(2,10): # for i in range(x,y), here y should be around or <= sqrt(101)
    l = filter(lambda x: x==i or x%i, l)

print l

for num in range(1,101):
    prime = True
    for i in range(2,num/2):
        if (num%i==0):
            prime = False
    if prime:
       print num

0

Comment à ce sujet? La lecture de toutes les suggestions que j'ai utilisé ceci:
```
prime=[2]+[num for num in xrange(3,m+1,2) if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1))]
```
Les nombres premiers jusqu'à 1000000
```
root@nfs:/pywork# time python prime.py
```
78498

réel 0m6.600

utilisateur 0m6.532s

sys 0m0.036s

f=0
sum=0
for i in range(1,101):
    for j in range(1,i+1):
        if(i%j==0):
            f=f+1
    if(f==2):
        sum=sum+i
        print i        
    f=0
print sum

La manière la plus rapide & meilleure mise en œuvre de l'omission sur les nombres premiers:

def PrimeRanges2(a, b):
    arr = range(a, b+1)
    up = int(math.sqrt(b)) + 1
    for d in range(2, up):
        arr = omit_multi(arr, d)

Ici est une approche différente que les métiers de l'espace pour une recherche plus rapide de temps. Cela peut être plus rapide.

import math

def primes(n):
    if n < 2:
        return []
    numbers = [0]*(n+1)
    primes = [2]
    # Mark all odd numbers as maybe prime, leave evens marked composite.
    for i in xrange(3, n+1, 2):
        numbers[i] = 1

    sqn = int(math.sqrt(n))
    # Starting with 3, look at each odd number.
    for i in xrange(3, len(numbers), 2):
        # Skip if composite.
        if numbers[i] == 0:
            continue
        # Number is prime.  Would have been marked as composite if there were
        # any smaller prime factors already examined.
        primes.append(i)
        if i > sqn:
            # All remaining odd numbers not marked composite must be prime.
            primes.extend([i for i in xrange(i+2, len(numbers), 2)
                           if numbers[i]])
            break
        # Mark all multiples of the prime as composite.  Check odd multiples.
        for r in xrange(i*i, len(numbers), i*2):
            numbers[r] = 0

    return primes

n = 1000000
p = primes(n)
print "Found", len(p), "primes <=", n

J'ai été inspiré par Igor et fait un bloc de code qui crée une liste:

def prime_number():

for num in range(2, 101):
    prime = True
    for i in range(2, num):
        if (num % i == 0):
            prime = False
    if prime and num not in num_list:
        num_list.append(num)
    else:
        pass
return num_list


num_list = []
prime_number()
print(num_list)

Ajoutant à la accepté de répondre, la poursuite de l'optimisation peut être obtenue en utilisant une liste de stocker des nombres premiers et de les imprimer après génération.

import math
Primes_Upto = 101
Primes = [2]
for num in range(3,Primes_Upto,2):
    if all(num%i!=0 for i in Primes):
       Primes.append(num)
for i in Primes:
    print i

num= int(input("Enter the numbner"))
isDivisible= False
int=2

while i<num:
    if num%i==0
    isDivisible True
    print("The number {} is divisible by {}.".format(num,i))
    i +=1

if isDivisible:
    print("The number {} is not prime.".format(num))
else:
    print("The number {} is a prime number.".format(num))

Ici est la plus simple logique pour les débutants d'obtenir les nombres premiers:

p=[]
for n in range(2,50):
    for k in range(2,50):
        if n%k ==0 and n !=k:
            break
        else:
            for t in p:
                if  n%t ==0:
                    break
            else:
                p.append(n)

print p

-1

Ajoutant ma propre version, juste pour montrer quelques itertools astuces v2.7:

import itertools

def Primes():
    primes = []
    a = 2
    while True:
        if all(itertools.imap(lambda p : a % p, primes)):
            yield a
            primes.append(a)
        a += 1

# Print the first 100 primes
for _, p in itertools.izip(xrange(100), Primes()):
    print p

Vous devez vous connecter pour publier un commentaire.