我如何减少空间复杂度中埃拉托塞尼的筛以生成a和b之间素？ [英] How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b?

问题描述

在通过一定的<一个得到href="http://stackoverflow.com/questions/622/most-efficient-$c$c-for-the-first-10000-prime-numbers">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.

这篇关于我如何减少空间复杂度中埃拉托塞尼的筛以生成a和b之间素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！