看板java
标 题Re: [问题] 作出可判断质数的程式
发信站无名小站 (Fri Sep 29 23:58:34 2006)
转信站ptt!ctu-reader!Spring!ctu-peer!news.nctu!netnews.csie.nctu!wretch
※ 引述《[email protected] (小安)》之铭言：
> ※ 引述《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 修改这篇文章