Prime Generator(用于SPOJ解决方案)

Question

我有几天的prime发电机算法解决SPOJ问题。问题状态在6秒内从数字m，N＆lt; = 1000000000打印至少100000个素数。我有这个实现，该实现在11.701067686080933秒中打印100000 Prime。是否可以在Python中击败时间限制（6s）。我觉得我错过了分段的筛子功能中的某些东西，因为我只是实施了它如何理解算法的工作，也许更改可以使它变得更好。

这里有一些帮助。

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()-后来的帖子编辑器将一个映射到另一个我假设是正确的。）sieveOfErosthen(j)返回什么？它返回一个数组，因此在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（十亿），我们必须假设最坏的情况，即6秒内的最后100,000个素数 segmentedSieve(m, 1000000000)将花费此代码分钟而不是秒。

最后，您没有实现分割的筛子 - 您实现了常规筛子，而只是脱离了请求的范围。我建议您阅读有关Wikipedia或其他地方的分段筛子的信息，如果您需要分段的筛子，请重新开始。

Answer 2

用于解决此问题，您必须使用分段的筛子。有一些很好的资源，请检查这些geeksforgeeksQuora

https://discuss.codechef.com/questions/54416/segented-sieve https://github.com/calmhandtitan/algorepo/blob/master/numbertheory/sieve_fast.fast.fast.cpp