降低Eratosthenes筛的空间复杂度,以生成一定范围内的质数 [英] Reducing space complexity of Sieve of Eratosthenes to generate primes in a range
问题描述
经过一些 SO帖子,我发现 Eratosthenes筛子是最好的&生成质数的最快方法.
After getting through some of the SO posts, I found Sieve of Eratosthenes is the best & fastest way of generating prime numbers.
我想生成两个数字之间的质数,例如 a
和 b
.
I want to generate the prime numbers between two numbers, say a
and b
.
AFAIK,按照Sieve的方法,空间复杂度为 O(b).
AFAIK, in Sieve's method, the space complexity is O(b).
PS:我写的是Big-O而不是Theta,因为我不知道是否可以减少空间需求.
PS: I wrote Big-O and not Theta, because I don't know whether the space requirement can be reduced.
我们可以减少筛网筛网的空间复杂度吗?
Can we reduce the space complexity in Sieve of Eratosthenes ?
推荐答案
如果您有足够的空间将所有素数存储到sqrt(b),则可以使用额外的空间O来筛选a到b范围内的素数(ba).
If you have enough space to store all the primes up to sqrt(b) then you can sieve for the primes in the range a to b using additional space O(b-a).
在Python中,它可能类似于:
In Python this might look like:
def primesieve(ps,start,n):
"""Sieve the interval [start,start+n) for primes.
Returns a list P of length n.
P[x]==1 if the number start+x is prime.
Relies on being given a list of primes in ps from 2 up to sqrt(start+n)."""
P=[1]*n
for p in ps:
for k in range((-start)%p,n,p):
if k+start<=p: continue
P[k]=0
return P
只需筛分奇数,就可以轻松地占用一半的空间.
You could easily make this take half the space by only sieving the odd numbers.
这篇关于降低Eratosthenes筛的空间复杂度,以生成一定范围内的质数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!