Java在线笔试编程（4）----计算质数

题目来自于2017年搜狗公司在线笔试。

题目如下：定义两个大于2的偶数之间的距离，为这两个数之间质数的个数。从小到大输入n个大于2的偶数，输出所有数两两之间距离的总和（应该有n*(n-1)/2个距离，输出总和就好）。

输入描述：

第一行是输入偶数的个数，最小为2，最大可能到几万，之后每行为一个偶数，最小为4，最大可能为到几百万，不重复的升序排列。

输出描述：

输入数据两两距离的总和，这应该是一个不小于0 的整数。

输入样例：

输出样例：

此题看起来求个质数嘛，很简单，其实是有点难度的，关键在于偶数可能为几百万，而规定的最大运行时间为4000ms。也就是要求复杂度不能过高。

这里我先给出常规的求质数的3个算法，第一个算法最慢，第二个次之，第三个最快。其中第二个、第三个方法参考至网上代码。

1.普通算法

private static int findZhiShu(int num) {
int counts = 0;
if (num < 2) {
return counts;
}
for (int i = 2; i <= num; i++) {
boolean isZhiShu = true;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isZhiShu = false;
break;
}
}
if (isZhiShu) {
System.out.print(i + " ");//输出质数
counts++;
}
}
return counts;
}

这个方法在10万左右时就比较耗时了。

2.优化算法

private static int findZhiShu(int num) {
int counts = 0;
if (num < 2) {
return counts;
}
for (int i = 2; i <= num; i++) {
boolean isZhiShu = true;
double index=Math.sqrt(i);
for (int j = 2; j <=index; j++) {
if (i % j == 0) {
isZhiShu = false;
break;
}
}
if (isZhiShu) {
System.out.print(i + " ");//输出质数
counts++;
}
}
return counts;
}

这里用到了取平方的方法，缩小了查找的范围，原因如下：

循环到sqrt（N）即可，简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，
2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。

这个方法只能在百万级以下的数时，在3秒以内。

3.进一步优化的算法

private static int findZhiShu(int n){  
        boolean[] primes= filterNumber(n);  
        int num=0;  
        if(primes!=null){  
            for(int i=1;i<primes.length;i++){  
                if(primes[i]){  
              //    System.out.print(i+" "); //打印质数
                  num++;
                }  
            }  
        }  
       // System.out.println("一共有"+num+"个质数");  
         return num; 
    }  
 //筛选法  
    private static boolean[] filterNumber(int num){  
        if(num<=0){  
            System.out.println("范围必须大于0");  
            return null;  
        }  
        boolean[] isPrime = new boolean[num + 1];  
        isPrime[1] = false;  
        Arrays.fill(isPrime,2,num,true);  
        int n = (int)Math.sqrt(num);  
        for(int i=1;i<=n;i++){  
            if(isPrime[i]){  
                for(int j=i*i;j<=num;j+=i){  //2*i改为i*i可以避免重复赋值，效率提升了约6%
                    isPrime[j]= false;  
                }  
            }  
        }  
        return isPrime;  
    }

用到的是筛选法。依次剔除2的倍数，3的倍数，5的倍数......

这个算法可以有效的对付9位数（上亿），我计算机测试输入123456789时，花费时间在3秒以内，在计算大数时，效率大约是第二种的80-100倍左右.

毫无疑问，必须得选第三种方法。

参考代码如下：

import java.util.Arrays;
import java.util.Scanner;

public class Test0 {

public static void main(String[] args) {
Scanner mScanner = new Scanner(System.in);
int len = mScanner.nextInt();
int counts = 0;
int array[] = new int[len];
for (int i = 0; i < len; i++) {
array[i] = mScanner.nextInt();
}
//  long time0=System.currentTimeMillis();
for (int i = 0; i < len-1; i++) {
for (int j = i+1; j < len; j++) {
counts += findZhiShu(array[j])-findZhiShu(array[i]);
}
}
//long time1=System.currentTimeMillis();

        System.out.println(counts);
    //  System.out.println((double)(time1-time0)/1000);


}
  //筛选法  
    private static boolean[] filterNumber(int num){  
        if(num<=0){  
            System.out.println("范围必须大于0");  
            return null;  
        }  
        boolean[] isPrime = new boolean[num + 1];  
        isPrime[1] = false;  
        Arrays.fill(isPrime,2,num,true);  
        int n = (int)Math.sqrt(num);  
        for(int i=1;i<=n;i++){  
            if(isPrime[i]){  
                for(int j=i*i;j<=num;j+=i){  //2*i改为i*i可以避免重复赋值，效率提升了约6%
                    isPrime[j]= false;  
                }  
            }  
        }  
        return isPrime;  
    }  

    private static int findZhiShu(int n){  
        boolean[] primes= filterNumber(n);  
        int num=0;  
        if(primes!=null){  
            for(int i=1;i<primes.length;i++){  
                if(primes[i]){  
              //    System.out.print(i+" "); //打印质数
                  num++;
                }  
            }  
        }  
       // System.out.println("一共有"+num+"个质数");  
         return num; 
    }  

}