判断素数及其算法优化

首先，我们要清楚什么是素数？

素数：又称质数，一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。

根据素数的定义，我们可以写成出判断一个数是不是素数的算法。

         /**
	  * 判断是否是素数
	  * @param n 目标数
	  * @return true：是素数; false:不是素数
	  */
	 public static boolean isPrime(int n){
		 //1不是素数
		 if(n<=1){
			 return false;
		 }
		 
		 for(int i=2;i*i<n;i++){//由于在找n的因数时，只需要除到n开根号，所以只需i*i<n即可
			 //只要能被i整除，则返回0
			  if(n%i==0){
				  return false;
			  }
		  }
		 return true;
	 }

我们知道如何判断一个数是不是素数后，就容易在给定的范围里寻找素数了。

不过，上面的判断素数的算法,在大范围内筛选素数的效率不是最高的。下面介绍一种Eratosthenes（埃拉托斯特尼）算法来进行素数的筛选，它的效率要高的多。

（1）先把1删除（1既不是质数也不是合数）

（2）读取队列中当前最小的数2，然后把2的倍数删去

（3）读取队列中当前最小的数3，然后把3的倍数删去

（4）读取队列中当前最小的数5，然后把5的倍数删去

.......

（n）读取队列中当前最小的状态为true的数n，然后把n的倍数删去

         /**
	  * Eratosthenes算法（用于筛选素数）
	  * @param primes 标记素数的数组
	  */
	 private static void Eratosthenes(boolean[] primes){
		 //数组的长度
		 int length=primes.length;
		 
		 //初始化数组，标志true代表是素数
		 for(int i=2;i<length;i++){
			 primes[i]=true;
		 }
		 
		 for(int i=2;i*i<length;i++){
			 //筛选素数
			 if(primes[i]){
				 for(int j=2*i;j<length;j++){
					 //不是素数，则继续筛选
					 if(!primes[j]){
						 continue;
					 }
					 //如果数j能被整除，则不是素数
					 if(j%i==0){
						 primes[j]=false;
					 }
				 }
			 }
		 }
	 }

下面我们使用分别上面的算法，传入一个测试用例来比较两个算法筛选素数的效率。

（1）使用Eratosthenes算法

 /**
     * 使用Eratosthenes算法寻找num以内的素数
     * @param num 目标数
     */
    public static void selectPrimesByEratosthenes(int num){
        //定义保存素数的数组
        boolean[] primes=new boolean[num+1];
        //统计素数个数
        int count=0;
        //调用Eratosthenes算法，筛选素数
        Eratosthenes(primes);
        //遍历出num内的所有素数
        for(int i=2;i<=num;i++){
            if(primes[i]){
                count++;
                System.out.println(i);
            }
        }
    }

测试代码：

 public static void main(String[] args) {
        //寻找100000以内的素数
        int n=100000;
        long start_time=System.currentTimeMillis();
        selectPrimesByEratosthenes(n);
        long end_time=System.currentTimeMillis();
        System.out.println("selectPrimesByEratosthenes:"+(double)(end_time-start_time)+" ms");

    }

（2）使用一般算法

 /**
     * 使用一般算法寻找素数
     * @param num
     */
    public static void selectPrimeByGenerate(int num){
        for(int i=2;i<=num;i++){
            if(isPrime(i)){
                System.out.println(i);
            }
        }
    }

测试代码：

 public static void main(String[] args) {
        //寻找100000以内的素数
        int n=100000;
        long start_time=System.currentTimeMillis();
        selectPrimesByGenerate(n);
        long end_time=System.currentTimeMillis();
        System.out.println("selectPrimesByGenerate:"+(double)(end_time-start_time)+" ms");

    }

比较时间：（这里的时间还加上了打印素数的时间）

所以，当在大范围内筛选素数时，Eratosthenes算法效率要高的多。