线性筛最终版

线性筛最终版

如果时间不充裕，很可能tle
有时候还是传统数组比较保险
快要蓝桥杯了，板子已经不会打了，发出来复习一下

vector<int> min_p;// 记录每个数的最小质因子
vector<int> primes;
void init_prime(int num){
    min_p.assign(num+1,0);
    for(int i = 2; i <= num; i++){
        if(min_p[i] == 0){
            primes.push_back(i);
            min_p[i] = i;
        }
        for(auto p : primes){
            if(i * p > num) break;
            min_p[i * p] = p;
            if(min_p[i] == p) break;
        }
    }
}