2570 绝对素数

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

新老客户大回馈,云服务器低至5折

2570 绝对素数

 

时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
 
 
 
 
题目描述 Description

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

输入描述 Input Description

输入正整数x

输出描述 Output Description

x位的绝对素数的数量

样例输入 Sample Input

1

样例输出 Sample Output

4

数据范围及提示 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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU--1358--KMP算法失配函数getfail()的理解--Period

下一篇:bzoj2809 [ APIO2012 ] -- 主席树