※ 引述《[email protected] (小安)》之铭言： : 【 在 [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 的运算方式差不多 : 而在一些琐碎的地方应该是更为精简 (这部分就纯粹只是个人观点了) 看看这个连结吧: http://primes.utm.edu/prove/prove4_3.html 对一个数检查是否为质数并不需要到 O(n^(1/2)) 喔 这个连结指出 O((log n)^12 f(log log n)) where f is a polynomial. 所以求质数的方法还可以再改进的 至少目前为止 po 出来的程式码都没有我所记录过的 code 还快 @_@ -- 是不是该移驾到 prob_solve 板讨论了呢 XD --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.115.205.85