用Python判斷質數的嘗試

周末開始Python的循環語句學習，於是就想到了一個經典的問題，尋找質數。這是第一次寶少用程序來解決實際的應用問題，看看會有什麼結果。

我們的目標是：輸入一個數字之後，讓計算機判斷它是不是質數。

拋出問題後，首先需要解決，什麼是質數的問題。與純數學的想法不同，我們需要找到一個可以讓計算機接受的判定的法則。

質數，就是除了1以及本身以外，沒有其他因數的自然數。首先它是個自然數，因此程序的輸入端就解決了，N=int（input（））。

重要的是判定的法則，沒有其他因數又可以表述成什麼呢？於是，要從簡單的數字舉例開始。問如何判定117是不是質數呢？我們會考慮分解117。

分解的過程其實是將這個數逐個地去試驗性除以2、3、5、……，只要能被整除，那麼就不是質數，如果一直找不到可以整除的數，那麼就是質數。

於是，寫出代碼如下：

N=int(input())
for i in range (2,N):
if N % i ==0:
print(N,"不是質數")
break
else:
print(N,"是質數")

運行結果正常，好像能夠判斷輸入的數字了。

那麼這裡有什麼可以改進的地方呢？

問題一：很明顯，如果輸入的數字是「1」的話，這個程序會輸出：1是質數。因此可以在前面進行輸入數字的判斷。

問題二：在數學上，進行質數判斷的計算，不會一直算到N-1這個數，只會算到N/2。因為除「1」以外，2是最小的因子了。

如果N，能夠找到大於N/2的因子的話，那麼另外一個因子就會小於2，這是不可能存在的。因此在循環的時候，我們計算到N/2就夠了，在程序運行上講，可以節省很大的運行時間。這在程序設計上是非常必要的。

通過這兩個分析，改進程序如下：

N=int(input())
if N>1:
for i in range (2,N//2+1):
if N % i ==0:
print(N,"不是質數")
break
else:
print(N,"是質數")
else:
print(N,"不是質數")

程序運行後，在輸入較大的數字時，運行的效率還是有提升的。
講完這些，想到了一道以前程序競賽的題目：輸入一串數字，請判斷出其中有多少個質數。

很明顯，這裡的實質問題還是要判斷輸入的一串數字裡面，每個數字是不是質數，然後還需要計數。因此，判斷質數的程序已經實現了，接下去是要解決輸入一串數字，然後逐個判斷，以及如何計數的問題。
數字需要一個一個放進去檢驗，然後出來一個結果，很容易想到使用一個函數定義的形式。
這裡我們定義了一個叫做judge的函數，判斷是否是質數，如果是質數，就把標記flag標記為「1」，不是則標記為「0」。同時，這樣也可以方便後面進行計數。

def judge(Num):
if Num > 1:
for i in range(2, Num // 2 + 1):
if Num % i == 0:
flag=0
break
else:
flag=1
else:
flag=0
return flag


N=int(input())
count=0
count=count+judge(N)
print("總共有",count," 個質數")

但是很明顯，這裡只能輸入一個數字，那麼如何進行多個數字的輸入呢？或者如何輸入一行用空格分隔的數字，再進行判斷有幾個質數呢？
要存入一串數字，很容易想到使用數組的概念。因為在scratch裡接觸過列表，所以這個還比較容易理解。然後，因為有空格，我們需要用split函數進行分割。

a=input()
N=[int(n) for n in a.split()]
l=len(N)
count=0
for i in range (l):
count=count+judge(N[i])
print("總共有",count," 個質數")

這裡涉及到後續數組的知識，以及split函數，只跟他講了一下大概，能夠看懂這個程序就可以了。