力扣204.计数质数（线性筛）

线性筛我之前的题解已经涉及到，但是讲的实在太差了我自己回看都看不懂，于是通过这道题重新回顾线性筛。

什么是线性筛？

我们的目的是要标记一个合数。我们知道合数一定可以写成（p,q等都是质因数，n,m是指数），其中一定会有一个最小的质数，我们让一个合数只会通过它的最小质因数所标记，这样该合数只会被标记一次，以做到线性时间复杂度。

具体而言怎么做。既然是找所有小于n的质数，我们就从2开始，从小到大往后遍历。

如果该数是质数，就加入质数数组。

然后用当前数乘上质数数组里的所有质数，将得到的每个积都标记为合数。这样每个合数都是通过一个质数数组里的质数标记的。

class Solution {
public:
    int countPrimes(int n) {
        vector<int> primes;//质数数组
        vector<int> isPrime(n,1);//标记，1代表质数，首先默认所有数都是质数
        for(int i=2;i<n;i++){
            if(isPrime[i]) primes.push_back(i);//如果当前数是质数，就加入质数数组
            for(int j=0;j<primes.size()&&i*primes[j]<n;j++){//遍历质数数组
                //让质数数组的每个质数乘上当前数，得到的积标记为合数
                isPrime[i*primes[j]]=0;
                //如果当前数是质数的倍数，则终止循环。
                if(i%primes[j]==0) break;
            }
        }
        return primes.size();
    }
};

对于break那部分。如果当前数i是primes[j]的倍数。假设不中断，对于i*primes[j+1]这个合数，它被primes[j+1]这个质数标记.但实际上，它的最小质数因该是primes[j],因为当i' =(i/primes[j])*primes[j+1]时，i' *primes[j]==i*primes[j+1],可知它因该被primes[j]这个质数标记。

当然不break中断的话也不会错，但是这样就显示不出线性筛的特点了。