Question

java,判断一个数是不是质数的程序？

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)的数就好了。

Answer 1

这是求素数中为了提高效率的一个的技巧

其实写成Math.sqrt(n)最好

为了提高效率,不用一定计算到n.

当然计算到n是没错的

-----------补充-----------

除去自身和1,能够整除一个数的最小值应该是2,最大值不会超过这个数的一半,所以不存在一个大于这个数一半的数能够整除这个数,所以在楼主的方法中只要计算到n/2就好了..

Answer 2

因为一个数的最小质子是2撒，所以你只要判断到n/2就可以了
对于18你就只需要判断到9就OK了，大于9的根本就不可能整除了（除了18，但是判断质数不需要它）

Answer 3

n也可以，只是没必要再用大于n/2得部分进行循环，因为一个数i>n/2时，n/i！=0，所以可以不用再循环。这样就提高了算法的效率。

Answer 4

/* 判断一个数是否是素数（质数） */
	public boolean isPrime(int number){
		for (int i = 2; i < number; i++){
			if(number%i == 0){
				return false;
			}
			continue;
		}
		return true;
	}

Answer 5

不用判断到二分之n吧，到根号n就可以了