※ 引述《decken (HAHAHA~)》之銘言：
: 大家好，
: 寫了一個求質數程式(列出1~1000000000之間所有質數)：
: http://i.imgur.com/WxDZQun.png?1
: def is_prime(num):
: if num == 2:
: return True
: if not num & 1:
: return False
這不算甚麼解法 然後我也很久沒有上數論了 有錯請指教
但理論上要檢查是不是質數的話 P = Q*R (Q&R !=1 1 < Q, R < P )
質數的定義是這樣的 當P可以被 Q and R整除的話
那他就不是質數 所以在我的定義之下 拿2 ~ P-1當中的所有數字去除P
只要餘0的話 那麼我們就可以說P不是質數
再來就是我們能不能讓check的範圍縮小呢?(畢竟2~P-1要檢查P-3次)
答案是有的(EX 證明 P > Q^2 這件事 對所有的 Q<P是不可能的就行了)
也就是 Q > sqrt(P)的數字以上就不用check了
(因為如果可以的話 R必定會在這之前讓你檢查到)
舉例來說 你找 101是不是質數 其實你loop只要check到11就可以了