區(qū)間素?cái)?shù)線性篩選

假設(shè)應(yīng)用場(chǎng)景為求一個(gè)區(qū)間長度遠(yuǎn)小于右端點(diǎn)的所有素?cái)?shù)，該區(qū)間為 。如若使用樸素素?cái)?shù)線性篩選，則需要的時(shí)間復(fù)雜度為 , 如果使用區(qū)間素?cái)?shù)線性篩選算法，則需要的時(shí)間復(fù)雜度為 .

思想

首先使用樸素素?cái)?shù)線性篩選算法獲得 的素?cái)?shù)集合 , 然后利用該集合的素?cái)?shù) 的 倍篩掉區(qū)間 的合數(shù)，其中

時(shí)間復(fù)雜度

設(shè)篩選區(qū)間為 的所有素?cái)?shù)。則由算法的特性可知，對(duì)于每個(gè)素?cái)?shù) ，均要篩掉 個(gè)合數(shù), 若區(qū)間的長度遠(yuǎn)小于區(qū)間右端點(diǎn)，則算法的時(shí)間復(fù)雜度花費(fèi)主要在 的素?cái)?shù)篩選上。

則總的時(shí)間復(fù)雜度為

即在該應(yīng)用場(chǎng)景下，可以以 的復(fù)雜度獲得該區(qū)間內(nèi)的所有素?cái)?shù)

代碼部分：

using array_int = vector<int>;
using array_int_ref = array_int &;
using array_bool = vector<bool>;
using array_bool_ref = array_bool &;

/***
樸素素?cái)?shù)線性篩選算法
**/
void regular_sieve(array_int_ref array, const int size) {
    // 使用sqrt(size)大小的素?cái)?shù)來進(jìn)行篩選，進(jìn)行優(yōu)化
    const int sqrt_size = sqrt(size) + 1;

    // 使用標(biāo)記數(shù)組進(jìn)行標(biāo)記是否為素?cái)?shù)
    array_bool is_prime(size + 1, true);
    for (int i = 2; i <= sqrt_size; ++i) {
        if (is_prime[i]) {

            // 使用i*i，進(jìn)行優(yōu)化
            for (int j = i * i; j <= size; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 清空無效數(shù)據(jù)
    array.clear();

    // 將標(biāo)記為素?cái)?shù)的數(shù)收集起來
    for (int i = 2; i <= size; ++i) {
        if (is_prime[i]) {
            array.push_back(i);
        }
    }
}

/***
區(qū)間素?cái)?shù)篩選算法
**/
void segment_sieve(array_int_ref array, const int l, const int r) {
    // 清空無效數(shù)據(jù)
    array.clear();

    // 判斷輸入范圍是否有效
    if (l > r) {
        return;
    }

    // 先使用樸素的線性素?cái)?shù)篩選算法，獲得[1, sqr(n)+1]內(nèi)的所有素?cái)?shù)
    const int sqrt_size = sqrt(r) + 1;
    const int total = r - l + 1;
    array_int sqrt_array;
    regular_sieve(sqrt_array, sqrt_size);

    // 利用樸素線性素?cái)?shù)篩選算法所獲得的素?cái)?shù)集合，篩選[l, r]內(nèi)的素?cái)?shù)集合
    array_bool is_prime(total + 1, true);
    for (int i = 0; i < sqrt_array.size(); ++i) {
        const auto& p = sqrt_array[i];

        // 獲取在區(qū)間[l, r]內(nèi)最小k_min倍p的合數(shù)c_min，k_min最小為2,
        int k_min = max(2, (l / p) + (l % p == 0 ? 0 : 1));
        int c_min = k_min * p;

        // 將區(qū)間[l, r]映射到[0, total-1],篩掉區(qū)間內(nèi)的合數(shù)
        for (int j = c_min - l; j < total; j += p) {
            is_prime[j] = false;
        }
    }

    // 將區(qū)間[0， total-1]所標(biāo)記的素?cái)?shù)映射到[l, r]內(nèi)，并將素?cái)?shù)添加到array數(shù)組
    for (int i = 0; i < total; ++i) {
        if (is_prime[i]) {
            array.push_back(i + l);
        }
    }
}