双重素数 时间限制：C/C++ 1000MS 内存限制：C/C++ 256MB

Question

双重素数
时间限制：C/C++ 1000MS
内存限制：C/C++ 256MB

描述

素数（质数）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。定义双重素数为这样的素数：它的各位数字之和也是一个素数。给定两个整数L 和 R，试确定在区间[L, R]内双重素数的个数。

输入描述

输入第一行包含一个整数 T，表示测试数据的组数。接下来每行一组测试数据，每组测试数据包含以空格分隔的两个整数 L 和 R。

1≤L≤R≤10 ^6。

对于 100% 的数据，1≤T≤100。

输出描述

每组测试数据输出一行，包含一个整数，表示在闭区间 [L, R] 内双重素数的个数。

样例输入 1

4
3 3
4 4
1 5
1 15
样例输出 1

1
0
3
5
提示

【数据范围】
对于100%的数据，1≤L≤R≤10 ^6，1≤T≤100 。

Answer 1

中午好🌞🌞🌞
本答案参考通义千问

要解决“双重素数”问题，我们需要找出在区间 [L, R] 内的所有素数，并且这些素数的各位数字之和也是素数。

---

一、问题分析

1. 什么是双重素数？

• 素数：只能被 1 和自身整除的自然数（如 2, 3, 5, 7 等）。
• 双重素数：一个素数，其各位数字之和也是一个素数。
  例如：
  • 23 是素数，2 + 3 = 5，5 也是素数 → 所以 23 是双重素数。
  • 11 是素数，1 + 1 = 2，2 也是素数 → 所以 11 是双重素数。

---

二、解题思路

步骤 1：预处理所有可能的素数（埃拉托斯特尼筛法）

由于 L 和 R 的范围是 1 到 10^6，我们可以使用 埃拉托斯特尼筛法 预处理出所有小于等于 10^6 的素数。

步骤 2：预处理每个数的数字和

对于每个数 n，计算它的各位数字之和。

步骤 3：预处理每个数是否为双重素数

对每个数 i，如果它是素数，并且其数字和也是素数，则标记为双重素数。

步骤 4：构建前缀和数组

为了快速回答查询 [L, R] 中有多少个双重素数，我们可以构建一个前缀和数组 prefix[i] 表示从 1 到 i 的双重素数个数。

这样每次查询只需要计算 prefix[R] - prefix[L-1] 即可。

---

三、算法实现步骤

1. 预处理素数表（筛法）

const int MAX = 1e6 + 1;
bool is_prime[MAX]; // 标记是否为素数
vector<bool> is_double_prime(MAX, false); // 标记是否为双重素数
vector<int> prefix_sum(MAX, 0); // 前缀和数组

// 初始化筛法
void sieve() {
    fill(is_prime, is_prime + MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i)
                is_prime[j] = false;
        }
    }
}

2. 计算数字和函数

int digit_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

3. 标记双重素数

void mark_double_primes() {
    for (int i = 2; i < MAX; ++i) {
        if (is_prime[i]) {
            int s = digit_sum(i);
            if (s < MAX && is_prime[s]) {
                is_double_prime[i] = true;
            }
        }
    }
}

4. 构建前缀和数组

void build_prefix_sum() {
    prefix_sum[0] = 0;
    for (int i = 1; i < MAX; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + (is_double_prime[i] ? 1 : 0);
    }
}

5. 查询函数

int query(int L, int R) {
    return prefix_sum[R] - prefix_sum[L - 1];
}

---

四、完整代码（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 1e6 + 1;
bool is_prime[MAX];
bool is_double_prime[MAX];
int prefix_sum[MAX];

// 步骤 1: 筛法求素数
void sieve() {
    fill(is_prime, is_prime + MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i)
                is_prime[j] = false;
        }
    }
}

// 步骤 2: 计算数字和
int digit_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// 步骤 3: 标记双重素数
void mark_double_primes() {
    for (int i = 2; i < MAX; ++i) {
        if (is_prime[i]) {
            int s = digit_sum(i);
            if (s < MAX && is_prime[s]) {
                is_double_prime[i] = true;
            }
        }
    }
}

// 步骤 4: 构建前缀和数组
void build_prefix_sum() {
    prefix_sum[0] = 0;
    for (int i = 1; i < MAX; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + (is_double_prime[i] ? 1 : 0);
    }
}

// 步骤 5: 查询
int query(int L, int R) {
    return prefix_sum[R] - prefix_sum[L - 1];
}

int main() {
    sieve();
    mark_double_primes();
    build_prefix_sum();

    int T;
    cin >> T;
    while (T--) {
        int L, R;
        cin >> L >> R;
        cout << query(L, R) << endl;
    }

    return 0;
}

---

五、复杂度分析

• 时间复杂度：O(N log log N)（筛法） + O(N)（双重素数标记） + O(N)（前缀和构建） + O(1)（每次查询）
• 空间复杂度：O(N)，用于存储素数、双重素数、前缀和等数组。

---

六、样例测试

输入样例：

1
4 3
3 4
4 1
5 1
15

输出样例：

1
1
0
3
5

---

七、总结

关键点：

• 使用筛法预处理素数；
• 对每个素数计算数字和；
• 检查数字和是否为素数；
• 构建前缀和数组，提高查询效率。

通过这种方式，我们可以在O(1) 时间内完成每个查询，非常适合大规模数据的处理。