UVa - 524 - Prime Ring Problem

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define S 100
8. using namespace std;
9.  
10. int n;
11. bool check[23];
12. int all[23];
13.  
14. bool prime[S];
15.  
16. void primeCheck(){
17.     int lim = sqrt(S);
18.     for(int i = 2; i <= lim; i++){
19.         if(prime[i]){
20.             for(int j = i*2; j <= S; j+=i){
21.                 prime[j] = false;
22.             }
23.         }
24.     }
25. }
26.  
27. bool sum(int a, int b){
28.     int c = a+b;
29.     return prime[c];
30. }
31.  
32. void PrimeRing(int ind){
33.     int p = all[ind-1]+all[ind-2];
34.     if(p > 1 && !prime[p])return;
35.     if(n == ind){
36.         if(sum(all[0], all[n-1])){
37.             for(int i = 0; i < n; i++){
38.                 printf("%d", all[i]);
39.                 if(i != n-1)printf(" ");
40.             }
41.             puts("");
42.         }
43.         return;
44.     }
45.     for(int i = 1; i < n; i++){
46.         if(!check[i]){
47.             all[ind] = i+1;
48.             check[i] = true;
49.             PrimeRing(ind+1);
50.             check[i] = false;
51.         }
52.     }
53. }
54.  
55. int main(){
56.     int cs = 0;
57.     memset(prime, true, sizeof(prime));
58.     primeCheck();
59.     while(scanf("%d", &n) == true){
60.         if(cs)puts("");
61.         memset(check, false, sizeof(check));
62.         memset(all, 0, sizeof(all));
63.         printf("Case %d:\n", ++cs);
64.         all[0] = 1;
65.         PrimeRing(1);
66.     }
67.     return 0;
68. }