1 条题解
-
0
#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
- 上传者