Advertisement
Saleh127

UVA 10742

Oct 19th, 2020
79
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. #define maX 1000108
  6. vector<ll>p;
  7. bool marked[maX];
  8. void sieve()
  9. {
  10. marked[0]=1;
  11. marked[1]=1;
  12. for(ll i=4;i<=maX;i+=2)
  13. {
  14. marked[i]=1;
  15. }
  16. p.push_back(2);
  17. for(ll i=3;i<=maX;i+=2)
  18. {
  19. if(marked[i]==0)
  20. {
  21. for(ll j=i*i; j<=maX; j+=i+i)
  22. {
  23. marked[j]=1;
  24. }
  25. }
  26. }
  27. for(ll i=3;i<=maX;i+=2)
  28. {
  29. if(marked[i]==0)
  30. {
  31. p.push_back(i);
  32. }
  33. }
  34. }
  35.  
  36. ll solve(ll a)
  37. {
  38. ll ans=0,lo,hi,mid,i,j,k,l;
  39. for(i=0;i<p.size() && a-p[i]>p[i];i++)
  40. {
  41. ll curentprime=a-p[i];
  42. lo=i+1;
  43. hi=p.size()-1;
  44. k=i;
  45. while(lo<=hi)
  46. {
  47. mid=(lo+hi)/2;
  48. if(p[mid]<=curentprime)
  49. {
  50. lo=mid+1;
  51. k=mid;
  52. }
  53. else hi=mid-1;
  54. }
  55. ans+=(k-i);
  56. }
  57. return ans;
  58. }
  59.  
  60. int main()
  61. {
  62. ios_base::sync_with_stdio(0);
  63. cin.tie(0);cout.tie(0);
  64.  
  65. sieve();
  66.  
  67. ll a,c=0,d;
  68. while(cin>>a && a)
  69. {
  70. cout<<"Case "<<++c<<": "<<solve(a)<<endl;
  71. }
  72.  
  73.  
  74. return 0;
  75. }
  76.  
Advertisement
RAW Paste Data Copied
Advertisement