区间素数线性筛选

假设应用场景为求一个区间长度远小于右端点的所有素数，该区间为 $[l, r]$ 。如若使用朴素素数线性筛选，则需要的时间复杂度为 $T(r)=rln(lnr)$ , 如果使用区间素数线性筛选算法，则需要的时间复杂度为 $T(r)=\sqrt{r} ln(ln \sqrt{r})$ .

思想

首先使用朴素素数线性筛选算法获得 $[1, \sqrt{r}]$ 的素数集合 $\Omega$ , 然后利用该集合的素数 $p_i$ 的 $k$ 倍筛掉区间 $[l, r]$ 的合数，其中
$k = max(2, \lceil\frac{l}{p_i}\rceil)$

时间复杂度

设筛选区间为 $[l, r]$ 的所有素数。则由算法的特性可知，对于每个素数 $p_i$ ，均要筛掉 $\lfloor\frac{r-l}{p_i}\rfloor$ 个合数, 若区间的长度远小于区间右端点，则算法的时间复杂度花费主要在 $[1, \sqrt{r}]$ 的素数筛选上。

则总的时间复杂度为

$T(r) = \sum_{p_i=2}^{\sqrt{r}}{\frac{r-l}{p_i}}=\sqrt{r}ln(ln\sqrt{r}),p_i\ is\ prime.$

即在该应用场景下，可以以 $\sqrt{n}$ 的复杂度获得该区间内的所有素数

代码部分：

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);
        }
    }
}

/***
区间素数筛选算法
**/
void segment_sieve(array_int_ref array, const int l, const int r) {
    // 清空无效数据
    array.clear();

    // 判断输入范围是否有效
    if (l > r) {
        return;
    }

    // 先使用朴素的线性素数筛选算法，获得[1, sqr(n)+1]内的所有素数
    const int sqrt_size = sqrt(r) + 1;
    const int total = r - l + 1;
    array_int sqrt_array;
    regular_sieve(sqrt_array, sqrt_size);

    // 利用朴素线性素数筛选算法所获得的素数集合，筛选[l, r]内的素数集合
    array_bool is_prime(total + 1, true);
    for (int i = 0; i < sqrt_array.size(); ++i) {
        const auto& p = sqrt_array[i];

        // 获取在区间[l, r]内最小k_min倍p的合数c_min，k_min最小为2,
        int k_min = max(2, (l / p) + (l % p == 0 ? 0 : 1));
        int c_min = k_min * p;

        // 将区间[l, r]映射到[0, total-1],筛掉区间内的合数
        for (int j = c_min - l; j < total; j += p) {
            is_prime[j] = false;
        }
    }

    // 将区间[0， total-1]所标记的素数映射到[l, r]内，并将素数添加到array数组
    for (int i = 0; i < total; ++i) {
        if (is_prime[i]) {
            array.push_back(i + l);
        }
    }
}

最后编辑于：2019.04.24 13:19:48