UC知道java,判断一个数是不是质数的程序？
来源：百度知道 编辑：UC知道 时间：2024/06/12 17:13:23
int n=18;
boolean t=true;
for(int i=2;i<=n/2;i++){
if(n%i==0){
t=false;
break;
我想问问for循环中的布尔表达式i<=n/2为什么我是n，谢谢！
这是提高效率的办法：
用n/2是因为一个数能被整除的最小的数是2.
比如举80的例子.
80是不能被任何大于40的数整除的.(自身除外)
所以不存在一个大于这个数一半的数能够整除这个数的..
用开方的原因是
比如36可以整除的数有
2 3 4 6 9 12 18(应该就是这些吧)
其实仔细观察就可以发现其实在36的平方根前后的数都是对称存在的,所以只要计算6之前(包括6)的数就好了。
boolean t=true;
for(int i=2;i<=n/2;i++){
if(n%i==0){
t=false;
break;
我想问问for循环中的布尔表达式i<=n/2为什么我是n，谢谢！
这是提高效率的办法：
用n/2是因为一个数能被整除的最小的数是2.
比如举80的例子.
80是不能被任何大于40的数整除的.(自身除外)
所以不存在一个大于这个数一半的数能够整除这个数的..
用开方的原因是
比如36可以整除的数有
2 3 4 6 9 12 18(应该就是这些吧)
其实仔细观察就可以发现其实在36的平方根前后的数都是对称存在的,所以只要计算6之前(包括6)的数就好了。
这是求素数中为了提高效率的一个的技巧
其实写成Math.sqrt(n)最好
为了提高效率,不用一定计算到n.
当然计算到n是没错的
-----------补充-----------
除去自身和1,能够整除一个数的最小值应该是2,最大值不会超过这个数的一半,所以不存在一个大于这个数一半的数能够整除这个数,所以在楼主的方法中只要计算到n/2就好了..
n也可以，只是没必要再用大于n/2得部分进行循环，因为一个数i>n/2时，n/i！=0，所以可以不用再循环。这样就提高了算法的效率。
因为一个数的最小质子是2撒，所以你只要判断到n/2就可以了
对于18你就只需要判断到9就OK了，大于9的根本就不可能整除了（除了18，但是判断质数不需要它）
不用判断到二分之n吧，到根号n就可以了
/* 判断一个数是否是素数（质数） */
public boolean isPrime(int number){
for (int i = 2; i < number; i++){
if(number%i == 0){
return false;
}
continue;
}
return true;
}