murugappan_s

Untitled

Sep 30th, 2018
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define pb push_back
  5. #define x first
  6. #define y second
  7. #define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  8. #define PI (atan(1)*4)
  9. #define mp make_pair
  10. using namespace std;
  11.  
  12. const int maxn = 1e9+2, lim = sqrt(maxn);
  13.  
  14. bitset<maxn> p(0);
  15.  
  16. inline void sieve() {
  17. p.set();
  18. p[1] = 0;
  19. for (register int i = 4; i < maxn; i += 2)
  20. p[i] = 0;
  21. for (register int i = 3; i <= lim; i += 2) {
  22. if (p[i]) {
  23. int st = i * i, add = 2 * i;
  24. for (register int j = st; j < maxn; j += add)
  25. p[j] = 0;
  26. }
  27.  
  28. }
  29. }
  30.  
  31. int main()
  32. {
  33. fastread;
  34. sieve();
  35. vector<int> losing;
  36. losing.pb(0);
  37. losing.pb(3);
  38. int lim=maxn-1;
  39. for(register int i=4;i<lim;i++){
  40. int win=0;
  41. for(auto u:losing){
  42. if(p[i-u+1]){
  43. win=1;
  44. break;
  45. }
  46. }
  47. if(win==0)
  48. losing.pb(i);
  49. }
  50. for(auto u:losing)
  51. cout<<u<<",";
  52. return 0;
  53. }
Add Comment
Please, Sign In to add comment