Python如何判斷一個正整數是否是素數?

素數（Prime Number），又稱質數，一個大於1的自然數，除了1和它自身外，不能整除其他自然數的數叫做質數；否則，稱為合數（Composite Number）。1既不是素數，也不是合數。

如2、3、5、7、11都是素數，因為找不到除了1和其本身之外的約數；而4、6、8都是合數，因為4可以整除2，6可以整除2和3，8可以整除2和4。

而一個數的約數必然是不超過該數的，加上素數必需是只有1和本身是其約數的條件。於是，我們可以通過枚舉小於該數，並且大於1的整數，來判斷該數是否是素數。

假設有一個正整數a，則其可以被寫成任意兩個正整數之積，即a = p * q。假設p < q，那么正整數p和q都是a的約數。注意到，如果我們知道p是a的約數，那麼可以通過q = a / p快速求得另外一個約數q。同樣的道理，如果某個數p不是a的約數，那麼q也不是a的約數。這就意味著我們在枚舉約數的時候，只需要枚舉2到不大於sqrt(a)的正整數即可。

雖然通過上述方法，已經能讓我們在根號級別的複雜度內，判斷一個正整數是否為素數。但是我們其實還可以做得更快！回到我們最初的起點，我們之所以要枚舉這些數，就是想找出原數的約數。然後除1外，任何一個正整數都能寫成多個素數的乘積的形式，所以我們枚舉特定範圍內的所有素數，也能達到相同的效果，而且數字範圍越大，其區間內素數個數和區間長度之比也將越來越小，大家可以看看下面不同區間內的素數統計結果：

從上圖的統計結果我們可以發現，我們用區間內的素數去判斷一個整數是否素數，比較的次數相較之前來說更少。雖然就單次判斷一個素數來說，這樣的算法可能並沒有優勢，因為還需要時間去求出該區間內的所有素數。但是如果需要判斷的數字很多，那麼先把該區間內的所有素數求出來，無疑是個更好的選擇。

而求不超過某個正整數x內的所有素數，有一個著名的算法——埃拉託斯特尼篩法。其算法描述為：

先用一個數組vis，把不大於該正整數x的所有正整數標記為0，表示沒有訪問；然後從第一個素數2開始遍歷整個區間，如果當前訪問的數沒有訪問過，則可以認為它是一個素數。那麼就將它在該區間內所有的倍數，全部標記為已訪問，這樣就保證外部的循環發現的沒有訪問過的數都是素數。其具體實現如下述代碼所示：

埃拉託斯特尼篩法

然而，除了上述篩法，還有其他高效的篩法，比如歐拉篩法，這裡只給出其代碼實現，希望大家能仔細去體會。

歐拉篩法

那麼Python如何判斷一個正整數是否是素數？我在這裡用math模塊實現