Cpir

区间质数统计（Count Primes in Range）是一个经典的算法问题，要求在给定的区间 [L, R] 内统计出所有的质数个数。质数是指大于1且只能被1和自身整除的正整数。

1、暴力枚举/试除法

暴力枚举/试除法是最朴素、最简单的一种求解区间质数的方法。它的思路非常简单：对于[L, R]区间内的每个整数i，我们都判断它是否为质数。判断一个数i是否为质数，只需要判断它能否被2到sqrt(i)之间的整数整除即可。如果i能够被2到sqrt(i)之间的整数整除，那么i就不是质数，否则i就是质数。

下面是C++的实现代码：

C++
#include <iostream>

using namespace std;

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int L, R;
    cout << "请输入区间[L, R]的左右端点L和R：" << endl;
    cin >> L >> R;
    int prime_num = 0;
    for (int i = L; i <= R; i++) {
        if (is_prime(i)) {
            prime_num++;
        }
    }
    cout << "区间内质数的数量为：" << prime_num << endl;
    return 0;
}

上述代码中，我们首先定义了一个is_prime函数，用于判断一个整数是否为质数。在主函数中，我们输入区间[L, R]的左右端点L和R，并用一个prime_num变量来存储区间内的质数数量。然后我们使用for循环遍历整个区间，对于每个数i，如果is_prime(i)返回true，说明它是一个质数，我们就将prime_num加1。最后输出区间内质数的数量。

2、区间筛法

区间筛法是一种较为高效的求解区间质数的方法，它的基本思想是在区间[L, R]内进行筛法，同时利用已知的质数集合S中的质数，通过标记法来得到区间内的质数。具体实现过程如下：

首先使用线性筛法预处理出[1, sqrt(R)]范围内的所有质数，并将它们存入集合S中。
对于[L, R]区间内的每个数i，初始化is_prime[i-L]为true。
遍历集合S中的每个质数p，从大于等于L/p的第一个整数开始，将区间[L, R]中所有p的倍数对应的is_prime[i-L]标记为false。
最后统计区间[L, R]中is_prime[i-L]为true的数量，即为区间内的质数数量。

区间筛法的时间复杂度为O((R-L+1)loglogR + sqrt(R)), 其中第一项是遍历S集合的复杂度，第二项是预处理质数的复杂度。可以看到，区间筛法的时间复杂度比试除法低得多，并且可以处理较大的区间。

下面是C++的实现代码：

C++
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1e7 + 5;

int L, R;
bool is_prime[MAXN]; // 记录[L, R]区间内的每个数是否为质数
vector<int> primes; // 存储[1, sqrt(R)]内的所有质数

void init_primes() {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAXN; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i * i < R; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
}

int main() {
    cout << "请输入区间[L, R]的左右端点L和R：" << endl;
    cin >> L >> R;
    init_primes();
    int prime_num = 0;
    bool is_prime_range[R - L + 1]; // 标记[L, R]区间内的每个数是否为质数
    memset(is_prime_range, true, sizeof(is_prime_range));
    for (int p : primes) {
        for (int i = max(p * p, (L + p - 1) / p * p); i <= R; i += p) {
            is_prime_range[i - L] = false;
        }
    }
    for (int i = L; i <= R; i++) {
        if (is_prime_range[i - L]) {
            prime_num++;
        }
    }
    cout << "区间内质数的数量为：" << prime_num;
    return 0;
}

下面再对上述代码进行详细解释：

首先在init_primes函数中预处理出[1, sqrt(R)]内的所有质数，并将它们存入集合primes中。这里使用了线性筛法进行预处理。

然后在主函数中，对于[L, R]区间内的每个数i，初始化is_prime_range[i-L]为true。

接着遍历集合primes中的每个质数p，从大于等于L/p的第一个整数开始，将区间[L, R]中所有p的倍数对应的is_prime_range[i-L]标记为false。

最后统计区间[L, R]中is_prime_range[i-L]为true的数量，即为区间内的质数数量。

需要注意的是，在第三步中，计算第一个不小于L且为p的倍数的整数时，需要使用(L + p - 1) / p * p来计算，而不能直接使用L / p * p，因为L / p向下取整会导致第一个不小于L且为p的倍数的整数不一定是L/p * p。

区间筛法的时间复杂度为O((R-L+1)loglogR + sqrt(R))，比暴力枚举/试除法的时间复杂度要低得多。

3、线性筛法 + 前缀和

线性筛法可以快速地求出一个数是否为质数，而前缀和则可以快速地统计区间内的数的数量。因此，我们可以使用线性筛法来求出区间内的所有质数，并使用前缀和统计质数的数量。时间复杂度为O(RloglogR)。

下面是一种使用线性筛法 + 前缀和的C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000000;  // 区间右端点
vector<bool> is_prime(MAXN + 1, true);
vector<int> prime_cnt(MAXN + 1, 0);

void linear_sieve() {
    for (int i = 2; i <= MAXN; i++) {
        if (is_prime[i]) {
            prime_cnt[i] = prime_cnt[i - 1] + 1;
            for (int j = i + i; j <= MAXN; j += i) {
                is_prime[j] = false;
            }
        } else {
            prime_cnt[i] = prime_cnt[i - 1];
        }
    }
}

int main() {
    linear_sieve();
    int L, R;
    cout << "请输入区间[L, R]的左右端点L和R：" << endl;
    cin >> L >> R;
    int prime_num = prime_cnt[R] - prime_cnt[L - 1];
    cout << "区间[" << L << ", " << R << "]内的质数数量为：" << prime_num << endl;
    return 0;
}

这个代码中，我们首先使用线性筛法求出区间内所有的质数，并使用前缀和求出区间内质数的数量。在主函数中，我们输入区间[L, R]的左右端点L和R，并输出区间内质数的数量。

需要注意的是，这个代码中使用了两个vector，一个is_prime用于判断一个数是否为质数，一个prime_cnt用于存储区间内质数的数量。在线性筛法中，我们首先将所有数都视为质数，然后从2开始，遍历到区间右端点，对于每个数i，如果它是质数，那么它就是区间内的一个质数，我们就将prime_cnt[i]设为prime_cnt[i-1]+1，并将i的所有倍数都标记为非质数；如果它不是质数，那么它不是区间内的一个质数，我们就将prime_cnt[i]设为prime_cnt[i-1]，并不进行其他操作。

在主函数中，我们首先调用linear_sieve()函数来求解区间内的所有质数，然后输入区间[L, R]的左右端点L和R，最后输出区间内质数的数量。

4、埃氏筛法

埃氏筛法是一种简单的筛法，可以用来求解区间内的所有质数。其原理与线性筛法类似，只不过它是从小到大遍历所有数，对于每个数i，如果它是质数，那么我们将i的所有倍数都标记为非质数。

下面是C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000000;  // 区间右端点
int prime_cnt[MAXN + 1];  // 区间内质数的数量
vector<bool> is_prime(MAXN + 1, true);  // 判断一个数是否为质数

void eratosthenes_sieve(int L, int R) {
    for (int i = 2; i * i <= R; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= R; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = L; i <= R; i++) {
        if (is_prime[i]) {
            prime_cnt[i - L]++;
            for (int j = i + i; j <= R; j += i) {
                prime_cnt[j - L]--;
            }
        }
    }
}

int main() {
    int L, R;
    cout << "请输入区间[L, R]的左右端点L和R：" << endl;
    cin >> L >> R;
    eratosthenes_sieve(L, R);
    int prime_num = 0;
    for (int i = L; i <= R; i++) {
        if (prime_cnt[i - L] == 1) {
            prime_num++;
        }
    }
    cout << "区间内质数的数量为：" << prime_num << endl;
    return 0;
}

上述代码中，我们首先使用埃氏筛法来求解区间[L, R]内所有的质数，并将它们的数量存储在prime_cnt中。然后我们遍历整个区间，对于每个数i，如果prime_cnt[i - L]为1，说明它是一个质数，我们就将prime_num加1。最后输出区间内质数的数量。

5、分块算法

分块算法可以将区间划分为若干个小块，对于每个小块，我们可以使用筛法或者Miller-Rabin算法来求解小块内的质数数量。然后将所有小块的质数数量相加即可得到区间内的质数数量。时间复杂度为O(sqrt(R)*RloglogR)，其中sqrt(R)为块的个数。

具体代码如下：

C++
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MAXN = 1000000;  // 区间右端点
int prime_cnt[MAXN + 1];  // 每个块内质数的数量
vector<bool> is_prime(MAXN + 1, true);  // 判断一个数是否为质数
vector<int> primes;  // 所有的质数

void linear_sieve() {
    for (int i = 2; i <= MAXN; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i + i; j <= MAXN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

void block_sieve(int L, int R) {
    vector<bool> block_is_prime(R - L + 1, true);
    int sqrt_R = sqrt(R);
    for (int p : primes) {
        if (p > sqrt_R) break;
        int start = max(p, (L + p - 1) / p) * p;
        for (int j = start; j <= R; j += p) {
            block_is_prime[j - L] = false;
        }
    }
    for (int i = L; i <= R; i++) {
        if (block_is_prime[i - L]) {
            prime_cnt[i - L]++;
        }
    }
}

int main() {
    linear_sieve();
    int L, R, block_size;
    cout << "请输入区间[L, R]的左右端点L和R：" << endl;
    cin >> L >> R;
    block_size = sqrt(R);
    for (int i = L; i <= R; i += block_size) {
        block_sieve(i, min(i + block_size - 1, R));
    }
    int prime_num = 0;
    for (int i = L; i <= R; i++) {
        if (is_prime[i]) {
            prime_num++;
        } else if (prime_cnt[i - L] > 0) {
            prime_num++;
        }
    }
    cout << "区间内质数的数量为：" << prime_num << endl;
    return 0;
}

6、欧拉筛法

欧拉筛法是一种高效的筛法，它的原理与线性筛法类似，但使用了一些优化技巧，可以更快地求解出区间内所有的质数。欧拉筛法的基本思想是：对于每个数i，我们只需要使用它前面的质数来筛选出它的倍数即可。具体地，我们用一个数组primes来存储前面所有的质数，然后对于每个数i，我们只需要用primes中的质数来筛选出它的倍数即可。由于primes中的质数都是从小到大排列的，所以当我们处理完i时，primes中的所有质数都小于i，因此我们可以保证primes中的所有质数都是i的因子。

下面是C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000000;  // 区间右端点
int prime_cnt[MAXN + 1];  // 区间内质数的数量
vector<int> primes;  // 存储所有质数

void euler_sieve(int L, int R) {
    vector<bool> is_prime(R - L + 1, true);
    for (int p : primes) {
        for (int i = max(p * p, (L + p - 1) / p * p); i <= R; i += p) {
            is_prime[i - L] = false;
        }
    }
    for (int i = L; i <= R; i++) {
        if (is_prime[i - L]) {
            prime_cnt[i - L]++;
            primes.push_back(i);
        }
    }
}

int main() {
    int L, R;
    cout << "请输入区间[L, R]的左右端点L和R：" << endl;
    cin >> L >> R;
    primes.push_back(2);
    euler_sieve(L, R);
    int prime_num = 0;
    for (int i = L; i <= R; i++) {
        if (prime_cnt[i - L] == 1) {
            prime_num++;
        }
    }
    cout << "区间内质数的数量为：" << prime_num << endl;
    return 0;
}

上述代码中，我们首先将2加入primes中，然后使用欧拉筛法来求解区间[L, R]内所有的质数，并将它们的数量存储在prime_cnt中。最后我们遍历整个区间，对于每个数i，如果prime_cnt[i - L]为1，说明它是一个质数，我们就将prime_num加1。最后输出区间内质数的数量。

*7、Miller-Rabin算法

Miller-Rabin算法是一种快速判断一个数是否为质数的算法，时间复杂度为O(klog3n)，其中k为测试次数，n为待判断的数。与试除法相比，Miller-Rabin算法在判断一个数是否为质数时，运算次数更少，因此更适合判断大数是否为质数。

Miller-Rabin算法的基本思路是：假设n为奇数，则可以将n-1表示成2^r* d的形式，其中r为非负整数，d为奇数。接着在[2, n-2]范围内随机选择k个整数a1、a2、...、ak，然后对于每个ai，都进行如下的测试：

若ai^d mod n = 1，则ai可能为n的一个见证人，进入下一个测试。
对于0 <= j <= r-1，若ai^ (2^j * d) mod n = n-1，则ai可能为n的一个见证人，进入下一个测试。
若上述两个测试都未通过，则ai为n的一个合数证据，n一定为合数，算法返回false。

对于一个合数n，如果进行k次测试，每次测试都没有找到一个证据，那么n很有可能为质数。根据费马小定理，当n为质数时，ai^(n-1) mod n = 1。因此，当n为质数时，每个ai都应该通过上述测试。

下面是用C++实现的Miller-Rabin算法的代码：

C++
// 快速幂，计算 (a^b) mod m
long long qpow(long long a, long long b, long long m) {
    long long res = 1 % m;
    a %= m;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

// 判断n是否为合数
bool MillerRabin(long long n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3 || n == 7 || n == 61 || n == 24251) return true; // 对于不大的数，可以直接判断是否为质数

    // 将n-1表示成2^r * d的形式
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        ++r;
    }

    // 进行k次测试
    for (int i = 0; i < 10; ++i) { // k=10，根据实验效果可调整，k越大，判断正确的概率越高
        long long a = rand() % (n - 2) + 2;
        long long x = qpow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        for (int j = 0; j < r - 1; ++j) {
            x = x * x % n;
            if (x == n - 1) break;
        }
        if (x != n - 1) return false;
    }
    return true;
}

Miller-Rabin算法的实现比较简单，其中用到了快速幂算法。上面代码中，选取了几个小的质数作为特判，如果待判断的数是这些数，则直接返回true。这里可以根据实际情况添加或删除特判的数。

在进行k次测试时，我选取了随机的ai进行测试。在实际使用中，根据实验效果可以调整k的值。一般来说，k越大，判断正确的概率越高，但是算法的运行时间也会相应增加。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用