转载地址：http://java.e800.com.cn/articles/2010/1110/1289376854382_1.html

　1. 根据概念判断:

如果一个正整数只有两个因子, 1和p，则称p为素数.

public boolean isPrime(int n)

{

if(n < 2) return false;

for(int i = 2; i < n; ++i)

if(n%i == 0) return false;

return true;

}

时间复杂度O(n).

2. 改进, 去掉偶数的判断

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), 速度提高一倍.

3. 进一步减少判断的范围

定理: 如果n不是素数, 则n有满足1< d

if(n < 2) return false;

for(int i = 0; primes[i]*primes[i]

int[] primeNums = new int[maxNum/2+1];

int sqrtRoot;

int cursor = 0;

boolean isPrime;

for(int i=2;i

if(primeNums[j]>sqrtRoot)

break;

if(i%primeNums[j]==0){

isPrime = false;

break;

}

}

if(isPrime){

primeNums[cursor++] = i;

}

}

int[] result = new int[cursor];

System.arraycopy(primeNums,0,result,0,cursor);

return result;

}

public static void main(String[] args) throws Exception{

int maxNum = Integer.parseInt(args[0]);

int[] primeNums = getPrimeNums(maxNum);

System.out.println("共"+primeNums.length+"个素数");

for(int i=0;i< primeNums.length;i++){

System.out.print(primeNums[i]+",\t");

}

}

}

6.(在素数表中)二分查找

Arrays.BinarySearch方法:

该方法用于在指定数组中查找给定的值，采用二分法实现，所以要求传入的数组已经是排序了的。

该方法的基本语法格式为：

Static int binarySearch(byte[] a, byte key)

该方法返回数据中key元素所在的位置，如果没有key元素，则返回key应插入的位置：-（insertion point-1），如数组中的第一个元素就大于key，返回-1。

注：数组的数据类型可以是int[] byte[] short[] float[] long[] double[] char[] Object[]类型。