※ 引述《tkcn.bbs@ptt.cc (小安)》之銘言：
> ※ 引述《TonyQ (骨頭)》之銘言：
> : 一萬個質數要怎麼找會比較有效率啊 真好奇XD
> 幾年前討論區也討論過質數問題
> 那時候有看到一個建立質數表的方法
> 如果是一萬個質數的話，
> 就先建立長度 10000 的 boolean 陣列 (當然用 bit 的方式也可以)
> 並初始化為 true
> 然後索引 i 從 2 開始，一但發現 true 即代表 i 為質數，
> 接著把所有小於 10000 的 i 的倍數都設成 false...依此類推
> 這就是建立質數表了，
> 比起對每個數檢查是否為質數應該會快不少
> 如果再配合 2 的倍數的處理，應該又可以省下一點時間
試試這個 i從2開始 一直到根號n
for(i=2;i<=sqrt(n);i++) {
if(n%i) {
system.out.println(n+"is prime number!");
i=n;
}
}
那它的時間複雜度降到n^(1/2)
--
夫兵者不祥之器物或惡之故有道者不處君子居則貴左用兵則貴右兵者不祥之器非君子
之器不得已而用之恬淡為上勝而不美而美之者是樂殺人夫樂殺人者則不可得志於天下
矣吉事尚左凶事尚右偏將軍居左上將軍居右言以喪禮處之殺人之眾以哀悲泣之戰勝以
喪禮處之道常無名樸雖小天下莫能臣侯王若能守之萬物將自賓天地相合以降甘露民莫
之令而自均始制有名名亦既有夫亦將知止知止218-175-77-185.dynamic.hinet.net海
Saren 在 06/09/29 23:58:34 從 218.175.77.185 修改這篇文章
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 7 之 9 篇)：