Prime Generator（用于 Spoj 解决方案）

Question

我花了好几天时间来研究这个 SPOJ 问题的素数生成器算法。问题状态是在 6 秒内从数字 m,n 打印至少 100000 个素数，其中 n<=1000000000。我有这个实现在 11.701067686080933 秒内打印 100000 个素数。是否有可能在 Python 中超过时间限制（6 秒）？我觉得我在分段筛功能中遗漏了一些东西，因为我只是按照我对算法工作的理解来实现它，也许改变可以让它变得更好。

在此提供一些帮助。

def sieveOfErosthen(m):
    limit=m+1
    prime=[True]*limit

    for i in range(2,int(m**0.5)):
        if prime[i]:
            for x in range(i*i,limit,i):
                prime[x]=False
    return prime  

def segmentedSieve(m,n):
    limit= n+1
    segment=[True]*limit

    for j in range(2,int(n**0.5) ):
        if sieveOfErosthen(j):
            for b in range(j*(m//j),limit,j):
                if b >j:
                    segment[b]=False
    for v in range(m,limit):
        if segment[v]:
            print(v)
    return True

Answer 1

这段代码是一场灾难。让我们从最明显的错误开始：

if sieveOfErosthen(j):

（这特别令人困惑，因为您的原始代码没有定义此函数，而是定义了 EratosthenesSieve()——后来您的 post 的编辑将一个映射到另一个，我假设是正确。） sieveOfErosthen(j) return 是什么？它 return 是一个数组，因此在 if 的布尔上下文中，此测试始终为 True，因为如果 j 为正，则数组始终包含至少一个元素！

将其更改为 if True: 并看到您的输出没有改变。剩下的是一个非常低效的筛选算法，我们可以通过各种方式加速它：

def segmentedSieve(m, n):
    primes = []
    limit = n + 1
    segment = [True] * limit

    if limit > 0:
        segment[0] = False

        if limit > 1:
            segment[1] = False

    for j in range(2, int(limit**0.5) + 1):
        if segment[j]:
            for b in range(j * j, limit, j):
                segment[b] = False

    for v in range(m, limit):
        if segment[v]:
            primes.append(v)

    return primes

这段代码可以很容易地在几分之一秒内找到前 100,000 个素数，但最终，如果 n <= 1000000000（十亿）那么我们必须假设最坏的情况，即最后 100,000 个素数在 6 segmentedSieve(m, 1000000000) 中一些合适的 m 秒，这将花费此代码分钟而不是秒。

最后，您没有实施 分段筛法 -- 您实施了常规筛法，只是略去了请求的范围。我建议您阅读 segmented sieves in Wikipedia 或其他文章，如果您需要分段筛子，请重新开始。

Answer 2

为了解决这个问题，你必须使用分段筛。有一些很好的资源请检查这些 geeksforgeeks quora

https://discuss.codechef.com/questions/54416/segmented-sieve https://github.com/calmhandtitan/algorepo/blob/master/numberTheory/sieve_fast.cpp

Prime Generator（用于 Spoj 解决方案）

Prime Generator(for Spoj solution)

python

algorithm

sieve-of-eratosthenes