генератор в Python, генерирующий простые числа

Question

Мне нужно сгенерировать простые числа, используя генератор в Python. Вот мой код:

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

У меня есть RuntimeError: максимальная глубина рекурсии превышена после 2-го prime.next(), когда я запускаю его.

Answer 1

genPrimes() безоговорочно называет себя точно такими же аргументами. Это приводит к бесконечной рекурсии.

Вот один из способов сделать это с помощью (нерекурсивную) генератор:

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 

Обратите внимание, что это оптимизированный для простоты и ясности, а не производительности.

Answer 2

Хороший, быстрый способ найти простые. n - это верхний предел для остановки поиска.

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

Самый быстрый способ генерации простых чисел - это сито. Здесь мы используем сегментированное сито Эратосфена для генерации простых чисел, по одному без максимума, по порядку; ps - список просеивающих пропусков меньше текущего максимума, а qs - это смещение наименьшего кратного соответствующего ps в текущем сегменте.

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 

Простой isPrime с помощью пробного деления достаточно, так как он будет ограничен корень четвертой степени из п. Размер сегмента 2 * delta произвольно установлен в 100000. Для этого метода требуется O (sqrt n) пространство для просеивающих простых чисел плюс постоянное пространство для сита.

Это медленнее, но экономит место для создания кандидатов простых чисел с колесом и проверяет кандидатов на первичность с помощью isPrime, основанных на сильных тестах псевдопроизведения на основаниях 2, 7 и 61; это справедливо для 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 

Если вы заинтересованы в программировании с простыми числами, я скромно рекомендую this essay в моем блоге.

Answer 4

Очень приятно! Вы просто забыли прекратить брать простые числа из внутреннего genPrimes(), когда достигнут квадратный корень x. Это все.

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 

Без этого вы соскабливаете глубокий конец или какое выражение. Когда змея ест собственный хвост, она должна остановиться посередине. Если он достигает своей головы, больше нет змеи (ну, направление еды здесь противоположное, но оно все еще применяется ...).

Answer 5

Просто немного более кратким:

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 

И вы можете использовать его как это:

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

Answer 6

Вот быстрый и четкий императив простой генератор не используется решета:

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 

Это почти идентично Ответ NPE, но включает в себя тест на корневой что значительно ускоряет генерацию больших простых чисел. Результатом является использование O (n) для списка primes.

Answer 7

Вот скрипт, который генерирует список простых чисел от 2 до заданного числа

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 

Это просто очередная реализация Sieve of Eratosthenes.