我已经研究了Eratosthenes的Sieve的工作,使用迭代生成到达给定数字的素数并且去掉所有复合数.并且算法只需要迭代到sqrt(n),其中n是我们需要找到所有素数的上限. 我们知道,与复合数的数量相比,最多n = 10 ^ 9的素数的数量非常少.因此,我们使用所有空间来通过标记它们的复合来告诉这些数字不是首要的.我的问题是我们可以修改算法只是存储素数,因为我们处理的范围非常大(因为素数的数量非常少)？我们可以直接存储素数吗？
algorithm optimization primes sieve-of-eratosthenes space-complexity