【 在 [email protected] () 的大作中提到: 】 : 试试这个 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) 对一个数检查是否为质数是只需 n^(1/2) 没错 但是这里应该用检查 n 个数来比较才是，所以应该是 n^(3/2) 而你所提的演算法其实是可以改进的， 只要把目前的 for 回圈的 i 改成只跑已经算出来的质数 (当然，同样是小於 sqrt(n) ) 也就是前面 TonyQ 所提过的方法 我所提的方法其实也是这样，虽然看起来是 O(n^2) 但其实与 TonyQ 的运算方式差不多 而在一些琐碎的地方应该是更为精简 (这部分就纯粹只是个人观点了) -- NPDA - Non-deterministic PushDown Automata (不确定是否推倒自动机) DPDA - Deterministic PushDown Automata (确定会推倒自动机) 得证: DPDA 效率比较高 ※ 来源:‧资讯传奇 inf.csie.thu.edu.tw‧[FROM: 59-126-173-31.HINET-IP.hinet.n]