Generador en Python generando números primos.

Necesito generar números primos usando el generador en Python. Aquí está mi código:

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

Tengo un RuntimeError: la profundidad de recursión máxima se excedió después del segundo prime.next () cuando lo ejecuté.

La forma más rápida de generar números primos es con un tamiz. Aquí utilizamos un tamiz segmentado de eratóstenes para generar los números primos, uno por uno sin máximo, en orden; ps es la lista de primos de cribado menores que el máximo actual y qs es el desplazamiento del múltiplo más pequeño del ps correspondiente en el segmento actual.

 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 simple isPrime usando la división de prueba es suficiente, ya que estará limitado a la cuarta raíz de n . El tamaño del segmento 2 * delta se establece arbitrariamente en 100000. Este método requiere O (sqrt n ) espacio para los primos de tamizado más espacio constante para el tamiz.

Es más lento, pero ahorra espacio para generar primos candidatos con una rueda y probar los candidatos para la primalidad con un isPrime basado en fuertes pruebas de pseudoprimo en las bases 2, 7 y 61; Esto es válido para 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 está interesado en progtwigr con números primos, recomiendo modestamente este ensayo en mi blog.

genPrimes() incondicionalmente se llama a sí mismo con exactamente los mismos argumentos. Esto lleva a la recursión infinita.

Aquí hay una forma de hacerlo usando un generador (no recursivo):

 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 

Tenga en cuenta que esto está optimizado para la simplicidad y la claridad en lugar del rendimiento.

Una buena y rápida forma de encontrar números primos. n es el límite superior para detener la búsqueda.

 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 

Muy bonito Acaba de olvidar dejar de tomar primos de genPrimes() interno genPrimes() cuando se alcanza la raíz cuadrada de x . Eso es todo.

 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 

Sin él, te deslizas fuera del extremo profundo, o cuál es la expresión. Cuando una serpiente come su propia cola, debe detenerse en el medio. Si llega a su cabeza, no hay más serpientes (bueno, la dirección de comer aquí es opuesta, pero aún se aplica …).

Solo un poco más conciso:

 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 

Y puedes usarlo así:

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

Aquí hay un generador primordial imperativo rápido y claro que no usa tamices:

 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 

Es casi idéntica a la respuesta de NPE , pero incluye una prueba de raíz que acelera significativamente la generación de primos grandes. El resultado es el uso del espacio O (n) para la lista de primes .

Aquí hay un script que genera una lista de números primos de 2 a un número dado

 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 

Esta es solo otra implementación de Tamiz de Eratóstenes .