查找特定的素數

這是我實現查找特定質數：查找特定的素數

import math 

def checkPrime(i): 
    if i == 3: 
     return True; 
    elif i == 2: 
     return True; 
    else: 
     count = 2; 
     prime = 2; 

     while count <= math.sqrt(i): 
      if (i % count == 0): 
       prime += 1; 
      count += 1; 

     if prime == 2: 
      return True; 
     else: 
      return False; 

x = 0; 
c = 2; 
while x < 10001: 
    if checkPrime(c) == True: 
     print c; 
     x += 1; 
    c += 1;

我用這個來找到10,001st素數（我從Project Euclid了一個問題）。但是，這似乎並不是解決問題的有效方法。它佔用了大量的計算能力（從執行完成需要大約20秒的事實可以看出）。我自己解決了這個問題，但花費的時間很艱鉅。

完成此問題最有效的方法是什麼？

P.S：我打印出所有的素數，以保持只看到偏好。這不是必需的。

來源

2014-03-12 Joseph Potts

所以......你的問題「是否有更好的方法，如果是的話是什麼？」 – Dannnno

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes – roippi

@Dannnno是的！對不起，我沒有澄清，編輯。 –

def fast_primes(max_n): 
    numbers = range(3, max_n+1, 2) 
    half = (max_n)//2 
    initial = 4 

    for step in xrange(3, max_n+1, 2): 
     for i in xrange(initial, half, step): 
      numbers[i-1] = 0 
     initial += 2*(step+1) 

     if initial > half: 
      return [2] + filter(None, numbers) 
start = 5 
tmp = [] 
while len(tmp) < 10001: 
    tmp=fast_primes(start) 
    start <<=1 

print tmp[10001]

似乎相當快是我（把我的邊際計算機上0.02秒）

來源

2014-03-12 22:00:39

哇！我剛開始在Eucler上解決問題，這是我第一次遇到執行時間問題。我認爲像這樣的實際編程真的會打開你的眼睛。我的實現需要40秒才能執行，你的速度非常快。去看看我現在編程的知識有多少。 –

，公平地說，這是優化的，以找到最大的總理，不到一定的價值...我相信你可以通過緩存和優化找到第n個總理來加速它 –

查找特定的素數

回答

相關問題