創作計劃

不少老師教編程，喜歡拿教大學那一套來教中學生。筆者認為這是不合适的，中學生有中學的學習方法。我認為從數學入手才能讓中學生更容易更快地融入編程。

01 餘數

02 約數與倍數

素數的定義是：除1外所有的正整數，如果僅僅能被自身和1整除，那麼稱為素數；

與素數對應的是合數：除1外所有的正整數，不是素數就是合數。

題1 判斷N是不是素數

N = eval(input("請輸入一個大于1的正整數:")) for i in range(2,N): if N % i == 0: print(f"{N}是合數") exit() # 用exit函數，不能用break。 print(f"{N}是素數")

這是根據定義來判斷的，但這不是一個最好的辦法。

題2 埃氏算法

埃氏指的是埃拉特色尼。埃拉特色尼是古希臘時代的地理學家和數學家，是人類曆史上第一個正确測量地球半徑的人。

這個算法的精髓在于，判斷N是否為素數，不用判斷N能否被N-1整除。實際上，過了N的一半，N就沒法整除了。如能把10整除（除自身外）的最大的數是5。所以，上述算法，完全可以省下一半的循環，但這還不是最省的。

令a×a≥n，如果n能整除2~a中間的某個整數的話，其商一定在a~n之間；如果n整除a~n之間的某個整數的話，其商一定在2~a之間。所以判斷n是否為素數的最省的方法是，看它能否被2~根号n的數整除。

如數字11，它的開方小于4，它不能被2,3整除，因此必為素數。

N = eval(input("請輸入一個大于1的正整數:")) sqrt_N = int(pow(N,0.5)) #int能取出整數部分，如int(1.5)=1。 #int(x),如果x>0,則int相當于向下取整， #如果x<0,則int相當于向上取整 for i in range(2,sqrt_N 1): if N % i == 0: print(f"{N}是合數") exit() # 用exit函數，不能用break。 print(f"{N}是素數")

題3 找出100以内的孿生素數

形如（3,5）（5,7）（11，13）的一對素數叫孿生素數。

def is_prime(n): sqrt_n = int(pow(n,0.5)) for i in range(2,sqrt_n 1): if n % i == 0: return False #return讓函數直接exit了 return True prime_list = [] for num in range(2,100): if is_prime(num) and is_prime(num 2): #注意and的執行順序，隻要當前一個是True時才會執行後一個 prime_list.append((num,num 2)) print(prime_list)

題4 素數列表

為什麼在此提素數列表呢？因為這個是很多精彩常考的題。如找出2019以内所有的素數。

我們用埃氏算法：

0. 建立2~N的數字列表
1. 從小到大，如果一個數字能被前面的數字整除，就把它删了。
2. 當執行到N的開方時，剩下的就是素數了。

如找出10以内的素數。

0. 建立數字列表[2,3,4,5,6,7,8,9,10]
1. 從2開始，凡是能被2整除（除2外）的就删了，剩下：[2,3,5,7,9]
2. 再删除3的倍數，剩下：[2,3,5,7]
3. 由于10的開方小于4，所以剩下的列表就是素數列表了。

這個算法适合人計算，對于計算機而言還要謹慎一點，關鍵點就在于，一個元素被删了之後，列表的下标要向前移動的。所以正确的做法是，從後往前删。

n = 2019 prime_list = list(range(2,n 1)) #建立列表 sqrt_n = int(pow(n, 0.5)) for i in range(2, sqrt_n 1): length = len(prime_list) for j in range(length-1,-1,-1): # 遍曆删除列表，要從後往前遍曆，否則會導緻越界 if (prime_list[j] % i == 0) and (prime_list[j] != i): prime_list.pop(j) print(prime_list)