C++ – 素数筛

struct prime_t {
    vector<bool> pri_flg; // 素数表 pri_flg[i] 表示 i 是否为素数
    vector<lli> pri_tab;  // 素数表 pri_tab[0~num] 保存着 0 ~ n 中的素数

    prime_t(lli n) : pri_flg(n + 1, true) { // 重置素数表 假设都是素数
        pri_flg[0] = pri_flg[1] = false;    // 规定 0 和 1 不是素数
        for (lli i = 2; i <= n; i++) {      // 遍历素数表
            if (pri_flg[i])
                pri_tab.push_back(i);                                         // 将素数存入素数表
            for (lli j = 0; j < pri_tab.size() && i * pri_tab[j] <= n; j++) { // 用每个数乘以素数集合里的数
                pri_flg[i * pri_tab[j]] = false;                              // 标记素数
                if (!(i % pri_tab[j])) break;                                 // 防止重复标记
            }
        }
    }
};