計數素數

Question

我是編程新手，在互聯網上發現了一個顯示第1000個素數的問題。但問題是，我的代碼，但我有一些問題。

count=0 
prime=[] 
n=2 

while count != 1000: 
    if n == 2 or n == 3 or n == 5 or n == 7 or n == 11: 
     prime.append(n) 
     n=n+1 
     count=count+1 
    elif n%2 == 0 or n%3 == 0 or n%5 == 0 or n%7 == 0 or n%11 == 0: 
     n=n+1 
    else: 
     prime.append(n) 
     n=n+1 
     count=count+1 

print(prime[999]) 

問題是當我有一些像403按照我寫的是黃金，但實際上它不是因爲它可以用13分和31

我想出了一個代碼解決方案，但我不知道如何去做，如果有更好的解決方案。如果你幫助我，請嘗試保存我的代碼，請不要給我全新的代碼。

我的解決方案是：

elif n%prime[:]==0 
    n=n+1 

所以基本上我想要做的是試圖把數403，例如，到任何一個我先前記錄的其他素數。但由於某種原因，這段代碼給了我一個錯誤。我想告訴節目「在列表中將n分配給每個號碼」。感謝您的幫助:)

Answer 1

您可以使用「任何」。

In [15]: prime = [2, 3, 5, 7, 11] 

In [16]: n = 15 

In [17]: any(n%p == 0 for p in prime) 
Out[17]: True 

In [18]: n = 17 

In [19]: any(n%p == 0 for p in prime) 
Out[19]: False 

In [20]: n = 19 

In [21]: any(n%p == 0 for p in prime) 
Out[21]: False 

基本上，它會告訴你給定的數字是否可以被列表中任何數字整除。

Answer 2

有幾種計算素數的算法，你首先需要的是先判斷函數isPrime（n）是否返回true或false，如果你需要這個函數isPrime（n）應該在o N）。有幾種方法來做到這一點，這裏有可能：

def isPrime(n): 
    i = 2; 

    while i*i < n: 
     if n % i == 0: 
      return false 
     i = i + 1 
    return true; 

這個人會給你素或不符合複雜度爲O（N^1/2），應該足以滿足你，在此之後，接下來的事情你需要做的是：

counter = 0 
number = 2 
while counter < 1000: 
    if isPrime(number): 
     counter = counter + 1; 
    number = number + 1 
print number; 

我還沒有試過這種代碼還沒有，但這個概念應該有