首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2570 绝对素数

2570 绝对素数

作者头像
attack
发布2018-04-13 12:18:24
7430
发布2018-04-13 12:18:24
举报

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 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-04-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2570 绝对素数
    • 分类标签 Tags 点此展开
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档