JakeLin

用户名：jake546

访问量：38438

签　名：

腾讯需要我！

等　　级
排　　名	39
经　　验	12638
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-题解1834：蓝桥杯2016年第七届真题-路径之谜（C++代码）-DFS/回溯+剪枝
浏览：286

JakeLin-2265题-蓝桥杯2015年第六届真题-移动距离-题解(C++代码)
浏览：280

JakeLin-1645题-[算法训练VIP]比赛安排-题解(C++代码)-简单模拟
浏览：250

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

JakeLin-1544题-蓝桥杯特殊的质数肋骨-题解(C++)-两种思路/带图详解

　　作者: JakeLin　　　　发表时间：2020-03-08 21:00:08 浏览：917　|　评论：2　

原题链接：蓝桥杯算法提高VIP-特殊的质数肋骨

**起初：**
看到质数的题目，并且还是多重质数，考效率呀！
贫道机智的小脑袋瓜Bling一闪，感觉事情并不简单，
**默默掏出筛选法的质数模板**，论效率咱就没被吊打过！

![](/image_editor_upload/20200308081005_18416.jpeg)
```cpp
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
bool Prime[99999999];
void buildPrime(int num){  //打表打表
	for(int i=2;i<sqrt(num);i++){
		for(int j=i*i;j<=num;j+=i){
			if(Prime[j]){
				Prime[j] = false;
			}
		}
	}
}
int main(){
	int n;
	cin>>n;
	int maxn = 9; int minn = 1;
	for(int i=2;i<=n;i++){
		maxn = maxn*10+9; minn = minn*10;
	}
	memset(Prime,true,sizeof(Prime));
	Prime[0]=Prime[1]=false;
	buildPrime(maxn);  //制作素数表
	for(int i=minn;i<=maxn;i++){
		int number = i;
		int tag = 1;
		while(number){
			if(!Prime[number]){ //数组查数，效率倍棒
				tag = 0;
				break;
			}else{
				number/=10;
			}
		}
		if(tag) cout<<i<<endl;
	}
	return 0;
}
```
一顿操作猛如虎，这题不过我二百五。

![](/image_editor_upload/20200308081828_43949.png)
... ...
OK,Fine。   ![](/image_editor_upload/20200308081939_62127.png)
八位数的情况目标范围是**10000000~99999999**，但我制作素数表的过程却还得**从2开始**做起，这就尴尬了.....

------------

**那再想想？**
1、第一位，也就是最高位，它是最后一根肋骨，那么肯定只能是质数2,3,5,7 了
2、其他位可以是1~9的数
**我们可以将其画成一棵树，它是下面这样的**
![](/image_editor_upload/20200308084152_26890.png)
以n=4（4位）为例，暴力搜索我们可以得到所有4位数的组合[2111,2112...等等],再对其进行判断质数与否即可。
但是题目**要求拆解后的数仍是质数**，所以我们在构造这个四位数时应该判断每一个中间过程是否为质数，若不是，则不需要继续遍历下去，讲得不好，或许看看图比较好理解：
![](/image_editor_upload/20200308084828_64127.png)
当你发现21不是质数了，那么后面的211，212...2111，2112...都不需要再去判断了，直接从22开始判断起来，这样子便省去了许多的无用功。
思路说清楚了，看一下完整的**DFS代码**：

```cpp
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n;
int a[]={2,3,5,7};
bool isPrime(int x){  //判断一个数是否是质数
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0) return false;
	}
	return true;
}
int dfs(int t,int step){ //step：层数，也即目前t的位数
	if(!isPrime(t)){  //t不是质数,跳回上一层
		return 0; 
	}else{
		if(step==n) {  //t达到n位时
			cout<<t<<endl;
			return 1;
		}
	}
	for(int i=1;i<=9;i++){
		step++;
		dfs(t*10+i,step); //t*10+i在原有t的基础上加了一位
		step--;  //"回过头来"，层数-1
	}
}
int main(){
	cin>>n;
	for(int i=0;i<4;i++){
		dfs(a[i],1);
	}
	return 0;
}
```
![](/image_editor_upload/20200308090000_67944.gif)

0.0分

20 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

你好

任何一位数都不能是偶数吧

2020-03-11 18:06:26

哪里有大佬哪里就有我

可以的

2020-03-08 21:07:52

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

JakeLin-1544题-蓝桥杯特殊的质数肋骨-题解(C++)-两种思路/带图详解

评论区

精彩推荐

震宇大神的杀毒软件（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

printf基础练习2 （C语言代码）

星期判断机（C语言代码）

交换Easy （C语言代码）

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

JakeLin-1544题-蓝桥杯特殊的质数肋骨-题解(C++)-两种思路/带图详解

评论区

精彩推荐

震宇大神的杀毒软件 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

printf基础练习2 （C语言代码）

星期判断机 （C语言代码）

交换Easy （C语言代码）

C二级辅导-温度转换（C语言代码）

　　评论区

震宇大神的杀毒软件（C语言代码）

星期判断机（C语言代码）