素數檢查功能故障

Question

我寫了一個函數來計算一個數是否爲素數，但嘗試它可能，它似乎無法給出正確的響應。它還打印正在遞增的n值。下面是函數的代碼（在Python，順便說一句）：

def isPrime(x): 
    for n in range(1, x): 
     print n 
     if x % n == 0: 
      return False 
    return True 

如果我輸入

isPrime(17) 

該函數返回

1 
False 

這是怎麼回事錯在這裏？

Answer 1

每個數字都可以被1整除，本身。質數是一個自然數，沒有正數除數其他比1和它本身。因此，如果您以1，開始for循環，則每個號碼x將在第一次迭代中通過條件x % 1 == 0，返回False。

要解決它，你需要用2，而不是1開始你的循環另外，作爲一個側面說明，你只需要循環2至sqrt(x)，因爲如果存在一些q > sqrt(x)劃分x，然後還必須有一個號碼p = x/q，它也分爲x和p < sqrt(x)。