质数筛选-筛选1-n的质数

质数：大于1的正整数，除了能被1或者其本身整除之外不能被其他数整除也叫素数，注意1不是正数

合数：大于1的正整数，可以被除了1和其本身整除

关于质数的几个常用性质：

1、假如x是质数，那么2x,3x,……都是合数

2、任何一个合数都可以分解为几个质数的积，且这种分解是唯一的

如何判断质数：

如果一个数不是质数那么一定满足x*y = num,其中x>1,y<num,x<y;因此1<x<=,所以遍历(1,]的所有的数，如果都能被num整除说明num是质数，反之不是

相关算法：

厄拉多塞筛法（埃氏筛）：如果x是质数那么2x,3x,……都是质数，具体做法遇到x是质数的时候就将2x,3x,4x......都标记为合数

优化：我们可以从x*x开始标记，因为2x,3x....(x-1)*x都被前面的数标记了（例如k*x，2<=k<x,k一定可以分为几个质数的乘积，因此k*x = p1*p2……*pk*x）

实现代码：

public int countPrimes(int n) {
        boolean[] visite = new boolean[n];  //标记质数
        Arrays.fill(visite, true);
        int ans = 0;                   //质数的数量
        for (int i = 2; i < n; i++) { //从2开始
            if (visite[i]) {
                ans++;
                if ((long) i * i < n) {   //防止数字大小越界
                    for (int m = i * i; m < n; m += i) {
                        visite[m] = false;
                    }
                }
            }
        }
        return ans;

    }

相关题型：leetcode