Saleh127

Prime Ring Problem

Sep 9th, 2020
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll pp[100];
  5. bool used[100],xx[100];
  6. ll n;
  7.  
  8. bool prime(ll cc)
  9. {
  10. for(ll i=2;i*i<=cc;i++)
  11. {
  12. if(cc%i==0)
  13. {
  14. return 0;
  15. }
  16. }
  17. return 1;
  18. }
  19.  
  20. void primetrack(ll ind)
  21. {
  22.  
  23. if(ind==n && xx[pp[n-1]+pp[0]])
  24. {
  25. cout<<pp[0];
  26. for(ll j=1;j<n;j++)
  27. {
  28. cout<<" "<<pp[j];
  29. }
  30.  
  31. cout<<endl;
  32. return;
  33.  
  34. }
  35.  
  36. for(ll i=2;i<=n;i++)
  37. {
  38. if(used[i]==0 && xx[pp[ind-1]+i])
  39. {
  40. used[i]=1;
  41. pp[ind]=i;
  42. primetrack(ind+1);
  43. used[i]=0;
  44. }
  45. }
  46.  
  47. return;
  48. }
  49.  
  50. int main()
  51. {
  52. ios_base::sync_with_stdio(0);
  53. cin.tie(0);cout.tie(0);
  54.  
  55. for(ll h=2;h<=40;h++)
  56. {
  57. xx[h]=prime(h);
  58. }
  59.  
  60. pp[0]=1;
  61. ll x=1;
  62. while(cin>>n)
  63. {
  64. if(x>1) cout<<endl;
  65. cout<<"Case "<<x<<":"<<endl;
  66. x++;
  67. primetrack(1);
  68. }
  69.  
  70.  
  71. return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment