Python中的生成器生成素数 [英] generator in Python generating prime numbers
问题描述
我需要在Python中使用生成器生成素数.这是我的代码:
I need to generate prime numbers using generator in Python. Here is my code:
def genPrimes():
yield 2
x=2
while True:
x+=1
for p in genPrimes():
if (x%p)==0:
break
else:
yield x
我遇到一个RuntimeError:在运行第二个prime.next()之后超过了最大递归深度.
I have a RuntimeError: maximum recursion depth exceeded after the 2nd prime.next() when I run it.
推荐答案
生成素数的最快方法是使用筛子.在这里,我们使用分割的Eratosthenes筛子依次生成素数,没有最大值. ps
是小于当前最大值的筛选质数列表,qs
是当前段中相应ps
的最小倍数的偏移量.
The fastest way to generate primes is with a sieve. Here we use a segmented Sieve of Eratosthenes to generate the primes, one by one with no maximum, in order; ps
is the list of sieving primes less than the current maximum and qs
is the offset of the smallest multiple of the corresponding ps
in the current segment.
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
就足够了,因为它将限于 n 的第四根.段大小2 * delta
任意设置为100000.此方法需要筛分质数的O(sqrt n )空间和筛分的恒定空间.
A simple isPrime
using trial division is sufficient, since it will be limited to the fourth root of n. The segment size 2 * delta
is arbitrarily set to 100000. This method requires O(sqrt n) space for the sieving primes plus constant space for the sieve.
它比较慢,但节省了用轮子生成候选素数并基于对2、7和61的强伪素数测试使用isPrime
测试候选素数的空间;这对2 ^ 32有效.
It is slower but saves space to generate candidate primes with a wheel and test the candidates for primality with an isPrime
based on strong pseudoprime tests to bases 2, 7, and 61; this is valid to 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
如果您对使用质数编程感兴趣,我建议在我的博客中这篇文章.
If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.
这篇关于Python中的生成器生成素数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!