※ 引述《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就可以了 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.58.140 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1447385029.A.792.html