public static boolean isPrime(int a) { boolean flag = true; if (a < 2) {// 素數不小于2 return false; } else { for (int i = 2; i <= Math.sqrt(a); i++) { if (a % i == 0) {// 若能被整除，則說明不是素數，返回false flag = false; break;// 跳出循環 } } } return flag; }
4 回答
已采納
JustWannaHugU
TA貢獻452條經驗 獲得超796個贊
同學，你不明白的地方是for (int i = 2; i <= Math.sqrt(a); i++)嗎？
這是一個素數運算定理，已經證明出來的，可以拿來直接用
定理: 如果n不是素數, 則n有滿足1<d<=sqrt(n)的一個因子d.
證明: 如果n不是素數, 則由定義n有一個因子d滿足1<d<n.
如果d大于sqrt(n), 則n/d是滿足1<n/d<=sqrt(n)的一個因子.
它的時間復雜度O(sqrt(n)/2), 比普通的素數算法速度提高O((n-sqrt(n))/2).
添加回答
舉報
0/150
提交
取消