我遇到一個c語言的問題,就是要寫出一百位數的質數,計算質數我會寫,但是要找出一百位數的質數,用double都存不下吧!!所以到底要用什麼方式來寫呢?
2006-04-25 20:53:54 · 3 個解答 · 發問者 超人五金 1 in 電腦與網際網路 ➔ 程式設計
我的問題是只要:隨機"輸出"一個一佰位的的質數。所以我如何作呢?謝謝!!
2006-04-26 06:17:08 · update #1
大數的質數判斷是跟一般的算法不同的一般的作法要算10位數就很慢了, 何況是100位.實務上, 大數的質數是用 米勒-拉賓檢驗[米勒-拉賓檢驗]for i = 1 to t do隨機挑選a,a介於2和n-2之間計算r = an-1 (mod n),過程中if $ X2≡1 (mod n) but X¹ ±1 (mod n) then output 「合數」if r ¹ 1 then output 「合數」output 「質數」可以參見http://tw.knowledge.yahoo.com/question/?qid=1306030706041
2006-04-26 12:11:43 補充:
其實Java有一個BigInteger的class裡面就有實作大數表示大數運算, 包括米勒-拉賓質數檢驗和隨機取特定位數的質數, 有興趣可以去java.sun.com下載src.jar檔
2006-04-26 12:14:43 補充:
有很多領域需要大的質數來做運算的要件, 密碼學就是其中之一, 100位的整數(你沒指明所以我假設是10進位)大概占三百多位元, 以現行的電腦運算能力來言是有需要這麼大的質數的.
2006-04-26 08:02:49 · answer #1 · answered by 瑪琪朵 5 · 0⤊ 0⤋
這就是所謂的"大數運算"問題
解法就是把每一位數字分別存到陣列中
運算的時候每一位都要自己去算
例如有兩個一百位數相加
123412.........................56789
+ 352355.........................32456
先算個位數得知和是15,所以最後加法結果的個位數是5
再算十位數,8+5再加上個位數的進位1=14,所以十位數是4
如此一直算到第一百位
總而言之就是"什麼都要自己來"就是了
這是我之前寫的大數四則運算和一百階層
是用C++寫的
你可以參考看看
http://www.wretch.cc/blog/swchen&article_id=4171713
P.S. 我比較好奇的是你要怎麼計算一個一百位的質數
在我的印象中這麼大的數很難判斷是不是質數
2006-04-26 06:47:15 · answer #2 · answered by Ivan 3 · 0⤊ 0⤋
如果只需要輸出就轉字串後結合輸出,如果需要運算就必須要拆解後分開運算再用字串結合輸出,如果方便告知的話,我很好奇你為何需要用到那麼大的數字?瑪雅天文已經很大了也沒弄到那麼大說。
2006-04-26 03:54:23 · answer #3 · answered by mindlight 2 · 0⤊ 0⤋