python | 挑戰一行質數程式碼

這幾天玩了一點python，不由得覺得這個語言真的很有趣很神奇，因為很多的運算和圈圈叉叉的lib，還有強大的documentation，官網上面還有自己的簡單tutorial，整個社群很強大。

在python的學習中，找質數算是第一個有點重要的練習，因為找質數的方法很多種，通常我們會用篩法刪去非質數的整數，最後剩下的就會是質數。所謂非質數的意思就是有因數可以將其整除(廢話)，所以我們可以這麼看這件事‧‧‧

 
#! usr/bin/evn python2.7
# -*- coding: utf-8 -*-

max = 100
primes = range(max)

for p in primes:
   if p > 1:
      print p,
   for s in primes[p*2::p]:
      primes[s] = 0
      
print primes

用下面的數列來表示這行程式碼會更生動：

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20...


第一次就直接刪掉不是質數的 1 和 0

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20...


印出 2 後，繼續往走到內層迴圈，刪掉範圍內所有 2 * n 的整數

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20...


第二次外層迴圈印出 3 後，繼續往走到內層迴圈，刪掉範圍內所有 3 * n 的整數

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20...


and so on... ，無論設定的max多少，都可以用刪除的篩法選出質數表。

這樣看起來已經是不得了了吧 : )



但是，好還要更好，python有幾個強悍的武器，融合使用起來真的是很威猛很方便，接下去我要挑戰的是一行程式碼求解質數表。

primes = [prime for prime in range(2, max) if all(prime % num for num in range(2, prime))]

這是上禮拜六晚上想到的解法，用all()來挑選出質數，算是all()的小練習。
不過我今天想到要使用python還有三大武器：

• map(function, list)
• filter(if_function, list)
• reduce(function, list)

質數既然是被過濾出來的，當然想到可以使用filter來篩：

filter(lambda prime: all(prime%num for num in range(2, prime)), range(2, max))

其實質數表的一行解很多人提出，大家都有自己的不同風格，還有用set()的差集去完成的，那也是很漂亮的解法。總之，毋庸置疑的是程式碼愈短執行速度就會快，尤其是有Comprehension方式的python，黏的好，整句code看起來就像是英文句子一樣自然流利而簡約。完整code請參見我的github

下次繼續挑戰一行程式碼！

May 1st, 2012

shesee @ Taipei