générateur en Python générant des nombres premiers

Question

J'ai besoin de générer des nombres premiers en utilisant un générateur en Python. Voici mon code:

def genPrimes(): 
    yield 2 
    x=2 
    while True: 
     x+=1 
     for p in genPrimes(): 
      if (x%p)==0: 
       break 
     else: 
      yield x 

J'ai RuntimeError: profondeur de récursivité maximale dépassée après la 2ème prime.next() quand je le lance. Inconditionnellement appelle lui-même avec exactement les mêmes arguments.

Answer 1

genPrimes() Cela conduit à une récursion infinie.

Voici une façon de le faire en utilisant un générateur (non récurrent):

def gen_primes(): 
    n = 2 
    primes = set() 
    while True: 
     for p in primes: 
      if n % p == 0: 
       break 
     else: 
      primes.add(n) 
      yield n 
     n += 1 

Notez que ceci est optimisé pour la simplicité et la clarté plutôt que la performance.

Answer 2

Un bon moyen rapide de trouver des primes. n est la limite supérieure pour arrêter la recherche.

def prime(i, primes): 
    for prime in primes: 
     if not (i == prime or i % prime): 
      return False 
    primes.add(i) 
    return i 

def find_primes(n): 
    primes = set([2]) 
    i, p = 2, 0 
    while True: 
     if prime(i, primes): 
      p += 1 
      if p == n: 
       return primes 
     i += 1 

Answer 3

Le moyen le plus rapide de générer des nombres premiers est un tamis. Ici, nous utilisons un tamis segmenté d'Ératosthènes pour générer les nombres premiers, un par un sans maximum, dans l'ordre; ps est la liste des nombres premiers de tamisage inférieure au maximum actuel et qs est le décalage du plus petit multiple du ps correspondant dans le segment en cours.

def genPrimes(): 
    def isPrime(n): 
     if n % 2 == 0: return n == 2 
     d = 3 
     while d * d <= n: 
      if n % d == 0: return False 
      d += 2 
     return True 
    def init(): # change to Sieve of Eratosthenes 
     ps, qs, sieve = [], [], [True] * 50000 
     p, m = 3, 0 
     while p * p <= 100000: 
      if isPrime(p): 
       ps.insert(0, p) 
       qs.insert(0, p + (p-1)/2) 
       m += 1 
      p += 2 
     for i in xrange(m): 
      for j in xrange(qs[i], 50000, ps[i]): 
       sieve[j] = False 
     return m, ps, qs, sieve 
    def advance(m, ps, qs, sieve, bottom): 
     for i in xrange(50000): sieve[i] = True 
     for i in xrange(m): 
      qs[i] = (qs[i] - 50000) % ps[i] 
     p = ps[0] + 2 
     while p * p <= bottom + 100000: 
      if isPrime(p): 
       ps.insert(0, p) 
       qs.insert(0, (p*p - bottom - 1)/2) 
       m += 1 
      p += 2 
     for i in xrange(m): 
      for j in xrange(qs[i], 50000, ps[i]): 
       sieve[j] = False 
     return m, ps, qs, sieve 
    m, ps, qs, sieve = init() 
    bottom, i = 0, 1 
    yield 2 
    while True: 
     if i == 50000: 
      bottom = bottom + 100000 
      m, ps, qs, sieve = advance(m, ps, qs, sieve, bottom) 
      i = 0 
     elif sieve[i]: 
      yield bottom + i + i + 1 
      i += 1 
     else: i += 1 

Un isPrime simple à l'aide Section de première instance est suffisante, car elle sera limitée à la racine quatrième de n. La taille de segment 2 * delta est arbitrairement fixée à 100000. Cette méthode nécessite l'espace O (sqrt n) pour les nombres premiers de tamisage plus l'espace constant pour le tamis.

Il est plus lent mais économise de l'espace pour générer des nombres premiers candidats avec une roue et tester les candidats pour la primalité avec un isPrime basé sur des tests de pseudoprime forts aux bases 2, 7 et 61; ceci est valable pour 2^32.

def genPrimes(): # valid to 2^32 
    def isPrime(n): 
     def isSpsp(n, a): 
      d, s = n-1, 0 
      while d % 2 == 0: 
       d /= 2; s += 1 
      t = pow(a,d,n) 
      if t == 1: return True 
      while s > 0: 
       if t == n-1: return True 
       t = (t*t) % n; s -= 1 
      return False 
     for p in [2, 7, 61]: 
      if n % p == 0: return n == p 
      if not isSpsp(n, p): return False 
     return True 
    w, wheel = 0, [1,2,2,4,2,4,2,4,6,2,6,4,2,4,\ 
     6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,\ 
     2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10] 
    p = 2; yield p 
    while True: 
     p = p + wheel[w] 
     w = 4 if w == 51 else w + 1 
     if isPrime(p): yield p 

Si vous êtes intéressé par la programmation avec des nombres premiers, je recommande modestement this essay sur mon blog.

Answer 4

Très très bien! Vous venez d'oublier d'arrêter de prendre des nombres premiers à partir de l'intérieur genPrimes() lorsque la racine carrée de x est atteinte. C'est tout.

def genPrimes(): 
    yield 2 
    x=2 
    while True: 
     x+=1 
     for p in genPrimes(): 
      if p*p > x:  # 
       yield x  # 
       break   # 
      if (x%p)==0: 
       break 
     # else: 
     # yield x 

Sans cela, vous faites glisser l'extrémité profonde, ou quelle est l'expression. Quand un serpent mange sa propre queue, il doit s'arrêter au milieu. Si elle atteint sa tête, il n'y a plus de serpent (bon, la direction de manger ici est en face, mais ça s'applique quand même ...).

Answer 5

Juste un peu plus concis:

import itertools 

def check_prime(n, primes): 
    for p in primes: 
     if not n % p: 
      return False 
    return True 

def prime_sieve(): 
    primes = set() 
    for n in itertools.count(2): 
     if check_prime(n, primes): 
      primes.add(n) 
      yield n 

Et vous pouvez l'utiliser comme ceci:

g = prime_sieve() 
    g.next() 
=> 2 
    g.next() 
=> 3 
    g.next() 
=> 5 
    g.next() 
=> 7 
    g.next() 
=> 11 

Answer 6

est ici un générateur premier rapide et clair impératif de ne pas utiliser des tamis:

def gen_primes(): 
    n = 2 
    primes = [] 
    while True: 
     is_prime = True 
     for p in primes: 
      if p*p > n: 
       break 
      if n % p == 0: 
       is_prime = False 
       break 
     if is_prime: 
      primes.append(n) 
      yield n 
     n += 1 

Il est presque identique à La réponse de NPE mais inclut un test de racine ce qui accélère considérablement la génération de grands nombres premiers. Le résultat est l'utilisation de l'espace O (n) pour la liste primes.

Answer 7

Voici un script qui génère la liste des nombres premiers de 2 à nombre donné

from math import sqrt 
next = 2 
n = int(raw_input()) 
y = [i for i in range(2, n+1)] 
while y.index(next)+1 != len(y) and next < sqrt(n): 
    y = filter(lambda x: x%next !=0 or x==next, y) 
    next = y[y.index(next)+1] 
print y 

Ceci est juste une autre mise en œuvre de Sieve of Eratosthenes.