【leetcode】204. 计数质数

class Solution {
public:
int prime[5000001];
int a[5000001] = {1,1};
int k = 0;
    int countPrimes(int n) {
        for(int i = 2;i < n; i++){
            if(a[i]==0){
                prime[++k] = i;//存质数
            }
            for(int j = 1;j <= k&&i*prime[j]<5000001; j++){
                if(i*prime[j]>5000001)break;
                a[i*prime[j]] = 1;//这个循环筛掉了当前数字的1到k倍
                if(i%prime[j]==0)break;//已经筛过的就直接跳过
            }
        }
        return k;//这里直接return个数
    }
};