在通过一定的SO帖子中,我发现埃拉托色尼的筛是最好的&放大器;生成素数的最快捷的方式。
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,在筛法,空间复杂度为O(B)。
AFAIK, in Sieve's method, the space complexity is O( b ).
PS:我写了大O,而不是西塔,因为我不知道这个空间的需求是否可以减少
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),则可以筛范围内的素数,以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.