[其他] 質數問題

看板Math作者 (軍曹)時間9年前 (2016/12/30 23:18), 編輯推噓5(5推 0噓 12→)
留言17則, 7人參與, 最新討論串3/3 (看更多)
內容蠻簡短的 但我想問的問題如下 1.如何判斷一個很大的數字是否是質數。 2.如何寫一個一萬以上的數字，並且保證他是質數。 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.125.114.57 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1483111119.A.702.html
→
12/30 23:20, , 1F
檢驗是否存在有小於其開根號的質因數
12/30 23:20, 1F
→
12/31 00:06, , 2F
(1)用手算的話, 同一樓
12/31 00:06, 2F
→
12/31 00:06, , 3F
12/31 00:06, 3F
→
12/31 00:08, , 4F
最簡單的就 n^2 + (n+1)^2
12/31 00:08, 4F
推
12/31 00:18, , 5F
從公式算不一定保證質數喔
12/31 00:18, 5F
→
12/31 00:18, , 6F
連結裡的列表都是「型如...的質數」
12/31 00:18, 6F
→
12/31 00:18, , 7F
並不是由這式子算出來都是質數
12/31 00:18, 7F
→
12/31 00:19, , 8F
拿上面舉的那型式為例, 3^2+4^2=5^2 就不是質數了
12/31 00:19, 8F
→
12/31 00:32, , 9F
原來如此, 難怪我記得好像沒有一個確定形式
12/31 00:32, 9F
推
12/31 00:50, , 10F
CKS質數測試
12/31 00:50, 10F
→
12/31 00:51, , 11F
雖然保證正確但並不實用
12/31 00:51, 11F
→
12/31 06:39, , 12F
aks吧
12/31 06:39, 12F
推
12/31 13:59, , 13F
感謝樓上更正
12/31 13:59, 13F
推
01/01 12:28, , 14F
查一下primality test
01/01 12:28, 14F
→
01/01 12:29, , 15F
我記得有一些方法不保證100%準確但是很快的方法
01/01 12:29, 15F
→
01/01 12:31, , 16F
實用上常常已經夠準了
01/01 12:31, 16F
推
01/01 14:48, , 17F
就是 Miller-Rabin 流吧
01/01 14:48, 17F
‣ 更多 kororoDX 的文章
文章代碼(AID): #1OPdhFS2 (Math)
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 kororoDX 的文章
文章代碼(AID): #1OPdhFS2 (Math)