UVA-542 Prime Ring Problem

#include
#include
#include
using namespace std;
const int maxn = 1000;
int prime[maxn];
int A[maxn];
int vis[maxn];
int is_prime(int x)// 
{
    for(int i = 2; i*i <= x; i++) if(x%i == 0) return 0;
    return 1;
}
void dfs(int n, int cur)
{
//    for(int i = 1; i <= cur; i++)
//        printf(i==1 ? "%d" : " %d", A[i]);
//    printf("
");
if(n < cur && prime[A[n]+1])// { for(int i = 1; i <= n; i++) printf(i==1 ? "%d" : " %d", A[i]); printf("
"
); return; } else { for(int i = 2; i <= n; i++) { if(prime[A[cur-1]+i] && !vis[i]) // { vis[i] = 1; A[cur] = i; dfs(n, cur+1); vis[i] = 0; A[cur] = 0; } } } } int main() { int n; for(int i = 2; i <= maxn; i++) prime[i] = is_prime(i); // for(int i = 0; i <= maxn; i++) // cout << prime[i] << endl; int t = 0; while(scanf("%d", &n) == 1 && n) { memset(A, 0, sizeof(A)); memset(vis, 0, sizeof(vis)); if(t) printf("
"
); printf("Case %d:
"
, t+1); A[1] = 1; dfs(n, 2); t++; } return 0; }

좋은 웹페이지 즐겨찾기