首页 > 代码库 > UVA524- Prime Ring Problem
UVA524- Prime Ring Problem
题目链接
题意:给出整数n,输出所有素数环
思路:回溯求解,注意输出时,每两组之间输出一个空行
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 105; int n; int arr[MAXN], prime[MAXN], vis[MAXN]; int is_prime(int x) { if (x == 2) return 1; for (int i = 2; i < MAXN; i++) if (x != i && x % i == 0) return 0; return 1; } void init() { for (int i = 2; i < MAXN; i++) prime[i] = is_prime(i); } void dfs(int cur) { if (cur == n && prime[arr[0] + arr[n - 1]]) { printf("%d", arr[0]); for (int i = 1; i < n; i++) printf(" %d", arr[i]); printf("\n"); } else { for (int i = 2; i <= n; i++) if (!vis[i] && prime[i + arr[cur - 1]]) { arr[cur] = i; vis[i] = 1; dfs(cur + 1); vis[i] = 0; } } } int main() { int t = 0; init(); while (scanf("%d", &n) != EOF) { arr[0] = 1; memset(vis, 0, sizeof(vis)); if (t) printf("\n"); printf("Case %d:\n", ++t); dfs(1); } return 0; }
题目链接题目链接
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。