首页 > 代码库 > 筛法求素数 6分

筛法求素数 6分

11:回文素数

  • 查看
  • 提交
  • 统计
  • 提问
总时间限制: 
5000ms
 
内存限制: 
65536kB
描述
一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文数,如121,1221,15651都是回文数。给定位数n,找出所有既是回文数又是素数的n位十进制数。(注:不考虑超过整型数范围的情况)。
输入
位数n,其中1<=n<=9。
输出
第一行输出满足条件的素数个数。
第二行按照从小到大的顺序输出所有满足条件的素数,两个数之间用一个空格区分。
样例输入
1
样例输出
42 3 5 7


 1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 int vis[100000001]; 7 int ans[100000001]; 8 int now; 9 int tot;10 int main()11 {12     int n;13     cin>>n;14     long long int fw=pow(10,n);15     long long int bg=pow(10,n-1);16     for(int i=2;i<=sqrt(fw+0.5);i++)17     {18         if(vis[i]==0)19         {20             for(int j=i*i;j<=fw;j=j+i)21             vis[j]=1;    22         }    23     }//筛法求素数 24     for(int i=bg;i<=fw;i++)//枚举范围内的每一个数 25     {26         if(vis[i]==1)continue;27         else28         {29             int sum=0,m;30             m=i;31             while(m)32             {33                 sum=sum*10+m%10;// sum为反复取的个位数加上次的sum的10倍34                 m/=10;//反复缩小10倍35             }36             if(sum==i)37             {38                 tot++;39                 ans[now]=i;40                 now++;41             }42         }43     }44     cout<<tot<<endl;45     for(int i=0;i<now;i++)46     cout<<ans[i]<<" ";47     return 0;48 }

 

筛法求素数 6分