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解決方案）

回答

相關問題