1 条题解

  • 0
    @ 2026-2-4 17:12:02
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] 输入的范围边界:n为左边界,m为右边界;sum为筛选出的素数个数
    int n,m,sum=0;
    // [2] 素数标记数组:arr[i]=1表示i是素数,arr[i]=0表示i是非素数,大小支持到1e8+100
    bool arr[100001000];
    // [3] 存储筛选出的素数的数组,大小预留足够空间
    int brr[9999999];
    
    // [10] 欧拉筛(线性筛)函数:筛选1~n范围内的所有素数,标记到arr数组并存储到brr数组
    void f(int n){
        // [11] 初始化标记数组,默认所有数为素数(1表示是素数)
        memset(arr,1,sizeof(arr));
        // [12] 遍历2到n的所有数,进行素数筛选
        for(int i=2;i<=n;i++){
            // [13] 如果当前数是素数,将其存入brr数组并计数
            if(arr[i]){
                brr[sum++]=i;
            }
            // [14] 用已筛选出的素数,标记当前数的倍数为非素数
            for(int j=0;j<sum&&brr[j]*i<=n;j++){
                arr[i*brr[j]]=0;  // [15] 标记i*brr[j]为非素数
                // [16] 若i能被当前素数brr[j]整除,说明后续倍数会被更小素数标记,提前终止循环
                if(i%brr[j]==0){
                    break;
                }
            }
        }
    }
    
    int main(){
        // [4] 输入范围的左右边界n和m
        cin>>n>>m;
        // [5] 调用欧拉筛函数,筛选1~m范围内的所有素数
        f(m);
        // [6] 遍历n到m的所有数,检查是否为素数且是回文数
        for(int i=n;i<=m;i++){
            // [7] 如果当前数不是素数,跳过后续检查
            if(arr[i]==0) continue;
            // [8] 反转当前数,判断是否为回文数
            int num=0,a=i;  // num存储反转后的数,a为当前数的临时变量
            while(a){
                num=num*10+a%10;  // 逐位反转当前数
                a/=10;
            }
            // [9] 如果反转后的数与原数相等,说明是回文数,输出该数
            if(num==i) cout<<i<<endl;
        }
        return 0; 
    }
    
    • 1

    信息

    ID
    1232
    时间
    1000ms
    内存
    512MiB
    难度
    2
    标签
    递交数
    5
    已通过
    1
    上传者