Prime Generator（用于Spoj解决方案）

我有几天在用SPOJ问题的Prime Generator算法挣扎。问题状态是在6秒钟内从数字m，n中打印至少100000个素数，其中n为< = 1000000000。我有这个实现在11.701067686080933秒内打印100000素数。是否有可能在Python中击败时间限制（6s）。我觉得我错过了我的分段筛选功能，因为我只是实现了它，我怎么理解算法的工作，也许一个改变可以使它变得更好。Prime Generator（用于Spoj解决方案）

在这里可以获得一些帮助。

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

来源

2017-09-03 steevie

请格式化你的代码，它包含几个语法错误。 – Pythonist

请参阅我的分段筛[HERE]（https://stackoverflow.com/a/10249801/448810）。 – user448810

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

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

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

最后，你没有实现分段筛 - 你实现了一个普通筛，只是撇去要求的范围内。我建议您阅读segmented sieves in Wikipedia或其他地方，如果您需要分段筛，请重新开始。

来源

2017-09-03 17:10:00 cdlane

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

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

来源

2017-09-03 18:06:20

Prime Generator（用于Spoj解决方案）

回答

相关问题