Simple Premier Générateur en Python

Il y a quelques problèmes:

• Pourquoi avez-vous l'impression de compter quand il n'en a pas diviser par x? Cela ne veut pas dire qu'il est premier, il signifie seulement que ce x ne divise pas, il
• continue se déplace à la prochaine itération de boucle - mais vous voulez vraiment arrêter à l'aide de break

Voici votre code avec quelques corrections, il imprime uniquement les nombres premiers:

import math

def main():
    count = 3
    
    while True:
        isprime = True
        
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break
        
        if isprime:
            print count
        
        count += 1

Pour beaucoup plus efficace premier génération, voir le Tamis de Erastothenes, comme d'autres l'ont suggéré. Voici une belle, optimisé mise en œuvre avec de nombreux commentaires:

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}
    
    # The running integer that's checked for primeness
    q = 2
    
    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        
        q += 1

Remarque qu'il renvoie d'un générateur.

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]

def primes(n): # simple Sieve of Eratosthenes 
   odds = range(3, n+1, 2)
   sieve = set(sum([range(q*q, n+1, q+q) for q in odds],[]))
   return [2] + [p for p in odds if p not in sieve]

>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Pour tester si un nombre est premier:

>>> 541 in primes(541)
True
>>> 543 in primes(543)
False

À mon avis, il est toujours préférable de prendre de l'approche fonctionnelle,

J'ai donc créer une fonction afin de savoir si le nombre est premier ou non, puis l'utiliser dans la boucle ou à une autre place que nécessaire.

def isprime(n):
      for x in range(2,n):
        if n%x == 0:
            return False
    return True

Puis exécutez une simple liste de compréhension ou de générateur d'expression pour obtenir votre liste de prime,

[x for x in range(1,100) if isprime(x)]

Comment à ce sujet si vous voulez calculer le premier directement:

def oprime(n):
counter = 0
b = 1
if n == 1:
    print 2
while counter < n-1:
    b = b + 2
    for a in range(2,b):
        if b % a == 0:
            break
    else:
        counter = counter + 1
        if counter == n-1:
            print b

Ici est un numpy version du Crible d'Eratosthène avoir tous les deux d'accord complexité (plus bas que le tri d'un tableau de longueur n) et la vectorisation.

import numpy as np 
def generate_primes(n):
    is_prime = np.ones(n+1,dtype=bool)
    is_prime[0:2] = False
    for i in range(int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.where(is_prime)[0]

Horaires:

import time    
for i in range(2,10):
    timer =time.time()
    generate_primes(10**i)
    print('n = 10^',i,' time =', round(time.time()-timer,6))

>> n = 10^ 2  time = 5.6e-05
>> n = 10^ 3  time = 6.4e-05
>> n = 10^ 4  time = 0.000114
>> n = 10^ 5  time = 0.000593
>> n = 10^ 6  time = 0.00467
>> n = 10^ 7  time = 0.177758
>> n = 10^ 8  time = 1.701312
>> n = 10^ 9  time = 19.322478

Vous devez vous assurer que tous les diviseurs de ne pas répartir uniformément le numéro que vous désirez vérifier. Dans ce cas, vous allez imprimer le nombre que vous êtes à la vérification de tous les temps juste l'un des diviseurs de ne pas répartir uniformément le nombre.

Aussi, vous ne voulez pas utiliser une instruction continue parce que a va juste provoquer des afin de vérifier la prochaine diviseur quand vous l'avez déjà constaté que le nombre n'est pas un nombre premier.

Vous pouvez créer une liste de nombres premiers en utilisant la liste des compréhensions et d'une manière très élégante manière. Prises de ici:

>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Similaire à user107745, mais l'utilisation de "tous" au lieu de la double négation (un peu plus lisible, mais je pense que même performance):

import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]

Fondamentalement, il parcourt le x dans la gamme de (2, 100) et de la cueillette seulement ceux qui n'ont pas mod == 0 pour tout t in range(2,x)

Une autre façon est probablement juste de peupler le premier des nombres, comme nous allons:

primes = set()
def isPrime(x):
  if x in primes:
    return x
  for i in primes:
    if not x % i:
      return None
  else:
    primes.add(x)
    return x

filter(isPrime, range(2,10000))

SymPy est une bibliothèque Python pour le calcul symbolique. Il offre plusieurs fonctions pour générer des nombres premiers.

isprime(n)              # Test if n is a prime number (True) or not (False).

primerange(a, b)        # Generate a list of all prime numbers in the range [a, b).
randprime(a, b)         # Return a random prime number in the range [a, b).
primepi(n)              # Return the number of prime numbers less than or equal to n.

prime(nth)              # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1)     # Return the largest prime smaller than n
nextprime(n)            # Return the ith prime greater than n

sieve.primerange(a, b)  # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes. 

Voici quelques exemples.

>>> import sympy
>>> 
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

À l'aide du générateur:

def primes(num):
    if 2 <= num:
        yield 2
    for i in range(3, num + 1, 2):
        if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
            yield i

Utilisation:

for i in primes(10):
    print(i)

2, 3, 5, 7

Pour moi, ci-dessous la solution semble simple et facile à suivre.

import math

def is_prime(num):

    if num < 2:
        return False

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

return True