今天第一次寫出miller-rabbin素數測試，知道這個概率算法對于大整數測試是否是素數十分有效，成功率有保證~于是突然想到有沒有手機號是素數！
電腦開了半個小時，用miller-rabbin測試，CPU一直保持占用率100%，結果搜結束之后我的data.out里面還是什么都沒有！
拿出紙筆，開始計算：如果手機號只有如下幾個限制：1、以1開頭；2、共11位。根據素數定理，手機號是素數的概率為0.04（以1開頭的11位整數大約有4億個是素數）。
很明顯，miller-rabbin出錯了！用5000-10000之間的素數對拍了一下，算法沒有出錯。毫無疑問，快速冪取模時溢出了！
換用O(n^0.5)的素數判斷，很快找到了許多素數手機號，列出幾個好的手機號吧：
15956880001；
15956880007；
15256880101；
15256888811；
15256885577
還有很多……
posted on 2010-02-20 23:26
lee1r 閱讀(547)
評論(0) 編輯 收藏 引用 所屬分類:
Programming Diary