確定一個數是否爲素數

Question

我知道這個問題已經討論過很多次了，我讀過它，但不知何故我無法得到它。 我想編寫一個程序來確定輸入的數字是否爲素數。

其中實現我發現某處在互聯網上：

from math import * 

def main(): 
    n = abs(input("Enter a number: ")) 
    i = 2 
    msg = 'is a prime number.' 
    while i <= sqrt(n): 
     if n % i == 0: 
      msg = 'is not a prime number.' 
     i = i + 1 
    print n, msg 


main() 

一對夫婦的問題在這裏：

• 在上面，什麼是i，爲什麼它有一個初始值的2？
• 是什麼i = i + 1做這個項目？
• 如何解釋知道什麼時候打印'is a prime number.'，即使它是從身體循環？

Answer 1

素數是一個數字，是隻能被1和自身整除。它使用的方法是嘗試將您的候選人編號從2到自身的其他數字除以n;但是，如果任何數量的i是你的號碼n的除數那麼這樣是n/i和其中至少有一個小於或等於sqrt(n)因此我們只需要測試多達sqrt(n)包容性。在實踐中，我們只需要測試實際上是素數的除數，但由於我們沒有素數列表，我們將測試每一個。

什麼在上面的i是？爲什麼它有兩個起始值？

i是我們正在測試的潛在因素n。它從2開始，因爲我們不在乎1分割n（並且它會很平凡），因爲素數定義允許/期望。

什麼是i = i + 1語句，在這個具體的例子中？在程序中看不到它的用處。

它在while i <= sqrt(n)定義的循環末尾遞增i;這意味着我們提前i測試n的下一個候選除數。

最後，python知道何時打印'是素數'。雖然它脫離了人體循環？

我們初始化msg爲「是一個素數」，如果我們發現任何除數然後我們把它改爲「是不是素數」的循環中。如果循環沒有找到除數，或者循環從不運行，我們將使用我們設置的「是一個素數」的初始值。順便說一句，你可以break當你找到除數的循環;那之後再進行測試沒有意義。

至於另一拋開你可能要計算sqrt(n)了一會兒，店外比在一個變量在while使用 - 你可能會重新計算平方根每次迭代，這是比較昂貴的。

Answer 2

我在兩側添加註釋來解釋每一行的作用：

from math import * # imports everything from the math module 

def main(): 
    n = abs(input("Enter a number: ")) # gets input from the user 
    i = 2 # starts off at 2 because all input is divisble by 1 
    msg = 'is a prime number.' # the message is initially set 
    while i <= sqrt(n): 
     if n % i == 0: # if 'i' divides evenly into n 
      msg = 'is not a prime number.' # only set if it isn't a prime 
     i = i + 1 # increases 'i' by 1 so it can check every value up to the square-root of 'n' (to see if it divides evenly) 
    print n, msg 


main() 

程序要經過的每i值（高達n平方根），使得每一個可能的因素被檢查。

這有點粗糙，主要檢查的，和低效的大型數字不是素數： 如果輸入的是一個數字，如1234567890，它會通過各種數量達迭代，以這個數字的平方根，這是35147（向上取整）。 使用return語句打破循環，因此您檢查的第一個數字2由於它可以被2整除，因此它被聲明爲不是素數。 通過使用return，它將停止該功能，併爲您節省35,146次計算。這不是一個龐大的數字（至少對於電腦來說），但它仍然具有更高的內存效率，並且需要更少的時間。

def isPrime(n): 
    '''Checks if 'n' is prime.''' 
    from math import sqrt 
    if n == 0 or n == 1: 
     return False 
    else: 
     for check in range(2, int(sqrt(n))+1): 
      if n % check == 0: return False 
    return True