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

淩亂°似流年 2022-09-26 00:22 165阅读 0赞

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

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

**输入描述：**

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

**输出描述：**

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

**输入样例：**

3
    4
    6
    12

**输出样例：**

此题看起来求个质数嘛，很简单，其实是有点难度的，关键在于偶数可能为几百万，而规定的最大运行时间为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; 
        }  
    
    }

后面给出我测试的结果

![Center][] ![Center 1][] ![Center 2][] ![Center 3][]

**对上面有什么疑问，欢迎交流指出，共同进步！**

[Center]: https://img-blog.csdn.net/20160913222524725?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20160913222534632?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20160913222542506?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: /images/20220717/d27de4d982f34041a89adb8eb8030fd0.png