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

Question

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

描述

素数（质数）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。定义幸运素数为这样的素数：它的各位数字既不为0，也分别都是素数。给定两个整数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
4
提示

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

Answer 1

让【宝码香车】来帮您解答，本回答参考DeepSeek编写，并整理提供。

如果答案让您满意，请采纳、点赞、关注，非常感谢！
.  
每日一句正能量，让它带给您好心情：困难像弹簧，你强它就弱，你弱它就强。
.  

幸运素数问题解答

问题分析

我们需要找出区间[L, R]内的"幸运素数"的数量。幸运素数需要满足两个条件：

1. 本身是素数
2. 它的每一位数字都是素数且不为0（即数字只能是2, 3, 5, 7）

解决思路

1. 预处理阶段：使用埃拉托斯特尼筛法预先计算所有素数
2. 对于每个素数，检查其每一位数字是否都是2, 3, 5, 7中的一个
3. 预处理所有幸运素数，并构建前缀和数组以便快速查询区间内的幸运素数数量

代码实现

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


const int MAX_N = 1e6 + 5;


vector<bool> is_prime(MAX_N, true);
vector<int> prefix_sum(MAX_N, 0);


// 初始化筛法和幸运素数前缀和
void init() {
    // 埃拉托斯特尼筛法
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAX_N; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX_N; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    // 构建幸运素数前缀和数组
    for (int i = 2; i < MAX_N; ++i) {
        bool is_lucky = is_prime[i];
        if (is_lucky) {
            int num = i;
            while (num > 0) {
                int digit = num % 10;
                if (digit != 2 && digit != 3 && digit != 5 && digit != 7) {
                    is_lucky = false;
                    break;
                }
                num /= 10;
            }
        }
        prefix_sum[i] = prefix_sum[i - 1] + (is_lucky ? 1 : 0);
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    init();
    
    int T;
    cin >> T;
    while (T--) {
        int L, R;
        cin >> L >> R;
        cout << prefix_sum[R] - prefix_sum[L - 1] << "\n";
    }
    
    return 0;
}

代码解释

1. 预处理阶段：
   • 使用埃拉托斯特尼筛法标记所有素数
   • 对于每个素数，检查其每一位数字是否都是2,3,5,7
   • 构建前缀和数组prefix_sum，其中prefix_sum[i]表示[1,i]区间内的幸运素数数量

1. 查询阶段：
   • 对于每个查询[L, R]，直接通过prefix_sum[R] - prefix_sum[L-1]得到结果
   • 这种方法使得每个查询的时间复杂度为O(1)

复杂度分析

• 预处理时间复杂度：O(n log log n)（筛法） + O(n * d)（数字检查），其中d是数字的平均位数
• 查询时间复杂度：O(1) 每个查询
• 空间复杂度：O(n)

这种方法对于题目给定的约束（n ≤ 1e6，T ≤ 100）非常高效。