首页 > > 程序设计 > C/C++ >

2570 绝对素数

2018-06-17 22:45:57来源：未知阅读 ()

2570 绝对素数

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

一个自然数是素数，且它的数字位置经过任意对换后仍为素数，则称为绝对素数，例如13。请找出所有x位的绝对素数的数量。

输入描述 Input Description

输入正整数x

输出描述 Output Description

x位的绝对素数的数量

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

x（x<=6)

分类标签 Tags 点此展开

DFS+筛法求素数

注意next_permutation的使用和i边界的控制

只要每次将生成的数进行判断就可以

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=100001;
 8 int vis[MAXN];
 9 int bc[MAXN];
10 int now=1;
11 int tot=0;
12 int f(int n)
13 {
14     if(n==0)return 1;
15     else return n*f(n-1);
16 }
17 int main()
18 {
19     int n;
20     scanf("%d",&n);
21     double bg=pow(10,n-1);
22     double ed=pow(10,n);
23     vis[1]=1;
24     for(int i=2;i<=sqrt(ed);i++)
25     {
26         if(vis[i]==0)
27         {
28             for(int j=i*i;j<=ed;j=j+i)
29             {
30                 vis[j]=1;
31             }
32         }
33     }
34     for(int i=(int)bg;i<=(int)ed-1;i++)
35     {
36         int flag=0;
37         int p=i;
38         if(vis[p]==1)continue;
39         memset(bc,0,sizeof(bc));
40         now=1;
41         while(p!=0)
42         {
43             bc[now]=p%10;
44             now++;
45             p=p/10;
46         }
47         for(int i=1;i<=f(now-1);i++)
48         {
49             next_permutation(bc+1,bc+now);
50             int ans=0;
51             for(int j=1;j<=now-1;j++)
52             {
53                 ans=ans*10+bc[j];
54             }
55             if(vis[ans]==1)
56             {
57                 flag=1;
58                 break;
59             }
60         }
61         if(flag==0)
62         tot++;
63     }
64     printf("%d",tot);
65     return 0;
66 }