Advertisement
Stepavly

Untitled

Jul 18th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.22 KB | None | 0 0
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("tune=native")
  3. #pragma GCC optimize("fast-math,unroll-loops")
  4.  
  5. #include <math.h>
  6. #include <algorithm>
  7. #include <set>
  8. #include <iostream>
  9. #include <vector>
  10. #include <queue>
  11. #include <map>
  12. #include <string>
  13. #include <time.h>
  14. #include <cassert>
  15. #include <functional>
  16. #include <memory.h>
  17. #include <stack>
  18. #include <bitset>
  19. #include <unordered_map>
  20. #include <unordered_set>
  21. #include <random>
  22. #include <chrono>
  23. #include <complex>
  24. #include <fstream>
  25. #include <climits>
  26. using namespace std;
  27.  
  28. typedef unsigned long long ull;
  29. typedef long long ll;
  30. typedef unsigned u;
  31. typedef long double ld;
  32. typedef vector<vector<int>> vvi;
  33. typedef unsigned char uc;
  34. typedef unsigned short us;
  35. typedef complex<double> cd;
  36.  
  37. #define INF 1000000000
  38. #define LLINF 1000000000000000000LL
  39. #define EPS 1e-9l
  40. #define pii pair<int, int>
  41.  
  42. const int DEBUG = 0;
  43.  
  44. #ifdef LOCAL
  45. mt19937 gen(228);
  46. #else
  47. mt19937 gen((u)chrono::high_resolution_clock::now().time_since_epoch().count());
  48. #endif
  49.  
  50. #pragma comment(linker, "/STACK:76777216")
  51.  
  52. vector<int> sieve(int n)
  53. {
  54. vector<char> a(n + 1, 0);
  55.  
  56. for (int i = 2; i * i <= n; i++)
  57. {
  58. for (int j = i * i; j <= n && !a[i]; j += i)
  59. {
  60. a[j] = 1;
  61. }
  62. }
  63.  
  64. vector<int> prime;
  65.  
  66. for (int i = 2; i <= n; i++)
  67. {
  68. if (!a[i])
  69. {
  70. prime.push_back(i);
  71. }
  72. }
  73.  
  74. return prime;
  75. }
  76.  
  77. int main()
  78. {
  79. ios_base::sync_with_stdio(0);
  80. cin.tie(0);
  81. cout.setf(cout.fixed);
  82. cout.precision(12);
  83. auto START_TIME = chrono::high_resolution_clock::now();
  84.  
  85. ll a, b;
  86. cin >> a >> b;
  87.  
  88. vector<int> prime = sieve(1000000);
  89.  
  90. if (b <= 1000000)
  91. {
  92. for (int p : prime)
  93. {
  94. if (p >= a && p <= b)
  95. {
  96. cout << p << " ";
  97. }
  98. }
  99.  
  100. return 0;
  101. }
  102.  
  103. vector<char> used(b - a + 1, 0);
  104.  
  105. for (int p : prime)
  106. {
  107. ll x = (a + p - 1) / p * p;
  108.  
  109. if (used[x - a])
  110. continue;
  111.  
  112. for (; x <= b; x += p)
  113. {
  114. used[x - a] = 1;
  115. }
  116. }
  117.  
  118. for (int i = 0; i < b - a + 1; i++)
  119. {
  120. if (!used[i])
  121. {
  122. cout << a + i << " ";
  123. }
  124. }
  125.  
  126. #ifdef LOCAL
  127. cerr.precision(3);
  128. cerr << "\nWorking time: " << chrono::duration<double>(chrono::high_resolution_clock::now() - START_TIME).count() << " sec.";
  129. #endif
  130.  
  131. return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement