素数线性筛选

素数的定义是除了1和自身能被整除外，没有其他数能被它整除。除此之外，1既不是素数，也不是合数。因此，素数是从2开始的。

思想

素数线性筛选是指根据素数的定义，合数为若干个素数的乘积。因此，可以利用已经确定的素数的K倍来筛掉不是素数的数。

时间复杂度

设筛选区间为 $[1, n]$ 的所有素数。则由算法的特性可知，对于每个素数 $p_i$ ，均要筛掉 $\lfloor\frac{n}{p_i}\rfloor-1$ 个合数, 每个合数为 $2p_i,3p_i,4p_i, ..., kp_i, kp_i<=n.$

则总的时间复杂度为

$T(n) = \sum_{p_i=2}^{n}{\frac{n}{p_i}}=nln(lnn),p_i\ is\ prime.$

由于 $ln(ln1000,0000) \approx 2.9134$ （一亿规模）, 故该算法又称为线性筛素数。

优化后的代码部分：

// 重定义类型
using array_int = vector<int>;
using array_int_ref = array_int &;
using array_bool = vector<bool>;
using array_bool_ref = array_bool &;

/***
朴素素数线性筛选算法
**/
void regular_sieve(array_int_ref array, const int size) {
    // 使用sqrt(size)大小的素数来进行筛选，进行优化
    const int sqrt_size = sqrt(size) + 1;

    // 使用标记数组进行标记是否为素数
    array_bool is_prime(size+1, true);
    for (int i = 2; i <= sqrt_size; ++i) {
        if (is_prime[i]) {

            // 使用i*i，进行优化
            for (int j = i * i; j <= size; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 清空无效数据
    array.clear();

    // 将标记为素数的数收集起来
    for (int i = 2; i <= size; ++i) {
        if (is_prime[i]) {
            array.push_back(i);
        }
    }
}