本文最后更新于 707 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
DFS
。
- 从小到大依次枚举所有的数显然不现实,因此考虑按位枚举。
- 枚举从最高位开始,之后枚举每一位的数,直到达到指定位数为止。
- 枚举每一位后,需要判断当前位的数和高位数的组合数是否为质数,只有如此才能满足条件。
- 举例说明对于 7331 的枚举过程:
- 第一位为 7,是质数,枚举下一位;
- 第二位为 3,和高位数组合为 73 是质数,枚举下一位;
- 第三位为 3,和高位数组合为 733 是质数,枚举下一位;
- 第四位为 1,和高位数组合为 7331 是质数,达到了位数条件即为所求。
- 由上述例子可知,最高位必定取值为 {2,3,5,7},且后续添加的数不能为偶数(从 1 枚举到 9 后续再判断也可以)。
- 因此,递归的每一层,枚举剩余位从 0 开始枚举到 9 与高位数组合判断。
- 若组合数为质数,则递归到下一层,否则跳过。
- 最终满足的组合数直接输出即可。
代码1(数组存方案版):
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n; |
| |
| int pos[] = {2, 3, 5, 7}; |
| int add[] = {1, 3, 5, 7, 9}; |
| |
| int ans[10]; |
| |
| bool is_prime(int x){ |
| if(x < 2) return 0; |
| for(int i = 2; i <= x / i; i ++){ |
| if(x % i == 0) return 0; |
| } |
| return 1; |
| } |
| |
| int sum(int u, int x){ |
| int t = 0; |
| for(int i = 0; i < u; i ++){ |
| t = t * 10 + ans[i]; |
| } |
| return t * 10 + x; |
| } |
| |
| void dfs(int u){ |
| if(u == n){ |
| for(int i = 0; i < u; i ++) cout << ans[i]; |
| cout << endl; |
| return ; |
| } |
| for(int i = 0; i < 5; i ++){ |
| if(is_prime(sum(u, add[i]))){ |
| ans[u] = add[i]; |
| dfs(u + 1); |
| } |
| } |
| } |
| |
| void solve(){ |
| cin >> n; |
| for(int i = 0; i < 4; i ++){ |
| ans[0] = pos[i]; |
| dfs(1); |
| } |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |
代码2(优化空间版):
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n; |
| |
| int pos[] = {2, 3, 5, 7}; |
| int add[] = {1, 3, 5, 7, 9}; |
| |
| bool is_prime(int x){ |
| if(x < 2) return 0; |
| for(int i = 2; i <= x / i; i ++){ |
| if(x % i == 0) return 0; |
| } |
| return 1; |
| } |
| |
| void dfs(int u, int ans){ |
| if(u == n){ |
| cout << ans << endl; |
| return ; |
| } |
| for(int i = 0; i < 5; i ++){ |
| int t = ans * 10 + add[i]; |
| if(is_prime(t)) dfs(u + 1, t); |
| } |
| } |
| |
| void solve(){ |
| cin >> n; |
| for(int i = 0; i < 4; i ++) dfs(1, pos[i]); |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |