2570 绝对素数

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 4768 跳石头

    4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

    attack
  • BZOJ4872: [Shoi2017]分手是祝愿

    Description Zeit und Raum trennen dich und mich. 时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n...

    attack
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • 程序员进阶之算法练习(四十六)

    题目链接 题目大意: 输入4个整数? , ?, ?, ?, 并且 ?≤?≤?≤?; 现在需要找三个整数?, ?, ?,满足: ?≤?≤?. ?≤?≤?...

    落影
  • C++ 函数重载

    C++允许用同一个函数名定义多个函数,而这些函数的参数个数和参数类型可以不相同。这就是函数重载。

    chaibubble
  • hdu ---(4517)小小明系列故事——游戏的烦恼(Dp)

    小小明系列故事——游戏的烦恼 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/327...

    Gxjun
  • 【编程经验】优秀题解

    今天给大家带来一个我站“Manchester”大神写的一份优质题解(j解题思路很清晰):原题问题:1709: 算法7-16:弗洛伊德最短路径算法:

    编程范 源代码公司
  • LeetCode Weekly Contest 31解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051
  • c++之数组

    绝命生

扫码关注云+社区

领取腾讯云代金券