[其他] 質數問題

[kororoDX (軍曹)]

內容蠻簡短的

但我想問的問題如下

1.如何判斷一個很大的數字是否是質數。

2.如何寫一個一萬以上的數字，並且保證他是質數。


謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.125.114.57
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1483111119.A.702.html
→ Marsden     : 檢驗是否存在有小於其開根號的質因數
→ OppOops     : (1)用手算的話, 同一樓
→ OppOops     : (2)http://tinyurl.com/gp2hdeg
→ OppOops     : 最簡單的就 n^2 + (n+1)^2
推 LPH66       : 從公式算不一定保證質數喔
→ LPH66       : 連結裡的列表都是「型如...的質數」
→ LPH66       : 並不是由這式子算出來都是質數
→ LPH66       : 拿上面舉的那型式為例, 3^2+4^2=5^2 就不是質數了
→ OppOops     : 原來如此, 難怪我記得好像沒有一個確定形式
推 atxp4869    : CKS質數測試
→ atxp4869    : 雖然保證正確但並不實用
→ ma4wanderer : aks吧
推 atxp4869    : 感謝樓上更正
推 wohtp       : 查一下primality test
→ wohtp       : 我記得有一些方法不保證100%準確但是很快的方法
→ wohtp       : 實用上常常已經夠準了
推 suhorng     : 就是 Miller-Rabin 流吧