Saleh127

uva 10168.cpp

Jun 3rd, 2020
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define test int t; cin>>t; while (t--)
  4. #define maX 20000005
  5. #define ll long long int
  6. bool marked[maX];
  7. void sieve()
  8. {
  9. marked[0]=true;
  10. marked[1]=true;
  11. for(ll i=4;i<=maX;i+=2)
  12. {
  13. marked[i]=true;
  14. }
  15. for(ll i=3;i*i<=maX;i+=2)
  16. {
  17. if(marked[i]==false)
  18. {
  19. for(ll j=i*i;j<=maX;j+=i+i)
  20. {
  21. marked[j]=true;
  22. }
  23. }
  24. }
  25. }
  26.  
  27. int main()
  28. {
  29. sieve();
  30. ll a,i,j,k,l;
  31. while(cin>>a)
  32. {
  33. j=0;
  34. if(a<8) printf("Impossible.\n");
  35. else
  36. {
  37. if(a%2==0)
  38. {
  39. printf("2 2 ");
  40. l=a-4;
  41. }
  42. else
  43. {
  44. printf("2 3 ");
  45. l=a-5;
  46. }
  47. for(i=0;i<a;i++)
  48. {
  49. if(marked[i]==false && marked[l-i]==false)
  50. {
  51. printf("%lld %lld\n",i,l-i);
  52. j=1;
  53. break;
  54. }
  55. }
  56. if(j==0) printf("Impossible.\n");
  57. }
  58. }
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment