sqrt(b)
的质数筛选范围[a..b]
("偏移"Eratosthenes筛法),或者通过奇数筛选。没错,就像消除每个质数的倍数一样消除每个奇数的倍数。将范围一次性筛选,或者如果范围太宽则分为几个“段”进行筛选(但是如果块太窄,则效率可能会降低)。-- foldl :: (r -> x -> r) -> r -> [x] -> r -- type signature of foldl
primesRange_by_Odds a b =
foldl (\ r x -> r `minus` [q x, q x+2*x .. b])
[o, o+2 .. b] -- initial value of `r`, the list
[3, 5 .. floor(sqrt(fromIntegral b))] -- values of `x`, one after another
where
o = 1 + 2*div a 2 -- odd start of the range
q x = x*x - 2*x*min 0 (div (x*x-o) (2*x)) -- 1st odd multiple of x >= x*x in range
sqrt(b)
以下,我们必须保留额外的空间O(pi(sqrt(b))) = ~ 2*sqrt(b)/log(b)
(其中pi()
是素数计数函数)。如果您有足够的空间来存储所有小于sqrt(b)的质数,那么您可以使用额外的O(b-a)空间筛选范围在a到b之间的质数。
在Python中,这可能看起来像:
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
通过仅筛选奇数,您可以轻松将其占用空间减少一半。
9,15,21...
或121,143,165...
),并且免费收集间隔中的质数。 - Will Ness(b-a)/log(b)
个),但结论是相同的。 - Will Ness