Re: [問題] Python 大數據處理
※ 引述《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://www.ptt.cc/bbs/Python/M.1447385029.A.792.html
→
11/13 13:48, , 1F
11/13 13:48, 1F
討論串 (同標題文章)