判断一个数是否是素数

1.排除偶函数

public boolean isPrime(int n){
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i < n; i += 2)
if(n%i == 0) return false;
return true;
}

时间复杂度O(n/2), 速度提高一倍.

进一步减少判断的范围
定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.

public boolean isPrime(int n){
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i*i <= n; i += 2)
if(n%i == 0) return false;
return true;
}