经典算法4质数筛 算法质数的判断 使用质数筛VS不使用质数筛性能比较

一、什么是质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

二、质数编程语言的判断

1. 对于很多数字a是否是质数的判断，我们需要每次都进行这样的操作：每个a都分别除以[2,a）中所有的数字，若不能被整除则认为这个数是质数。如果有很多这样子的a，我们知道每判断一个a要从新遍历a-2次，这样是非常浪费性能的。
2. 我们是否可以把从0到所求最大数字max的所有质数全部提前标注存起来呢？答案是可以的。
3. 实现思路：我们提前判断质数并都存到数组中（与0-max的数组下标与质数一一对应，是质数arr[x]==true,不是质数arr[x]==false），然后用数组下标直接取出true或false即可。这样的话，我们只需要遍历一次就解决了所有a的问题。
4. 下面我们用三种方法来判断质数，这三种方法性能逐渐优化

三、不使用质数筛

方法一：不做任何处理

    public static boolean judge(int i) {
        if (i<2) {
            return false;
        }

        for (int j=2;j<i;j++) {
            if (i%j==0) {
                return false;
            }
        }
        return true;
    }

方法二：对方法一进行优化

	private static boolean isPrime(int src) {
        double sqrt = Math.sqrt(src);
        if (src < 2) {
            return false;
        }
        if (src == 2 || src == 3) {
            return true;
        }
        if (src % 2 == 0) {// 先判断是否为偶数，若偶数就直接结束程序
            return false;
        }
        for (int i = 3; i <= sqrt; i+=2) {
            if (src % i == 0) {
                return false;
            }
        }
        return true;
    }

四、使用质数筛初始化保存

1.将质数存到数组中，便于后面使用时不用从新遍历，直接取用数组下标

   public static boolean isp[] = new boolean[a];
   public static void Init() {
        //初始化，默认都是质数
        for (int i=2;i< isp.length;i++) {
            isp[i]=true;
        }
        // 不是质数的变为false
        for (int i=2;i< isp.length;i++){
            if (isp[i]) {
                /**  不断更新	isp 数组
                 * 第一轮数组下标为2的倍数变为 false，
                 * 第二轮数组下标为3的倍数变为 false
                 * 第三轮数组下标为4的倍数变为 false
                 * ...
                 * 从2-a所有的质数全部初始化成功
                 */
                for(int j=i*2;j< isp.length;j+=i) {  //j从++变为+i，而i的值从2开始不断累加
                    //System.out.println(i+" "+j);
                    isp[j] = false;
                }
            }
        }
    }       

2.数组初始化成功，见下图

判断哪个数字是不是质数，直接取用isp数组下标即可。