fork download
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define int int64_t
  5. #define trav(i, a) for(auto& i: a)
  6. #define all(a) a.begin(), a.end()
  7. #define rall(a) a.rbegin(), a.rend()
  8. #define si(a) ((int)(a).size())
  9. #define ins insert
  10. #define pb push_back
  11. #define mp make_pair
  12. #define f first
  13. #define s second
  14.  
  15. const int MOD = 1e9 + 7;
  16. const int INF = 1e18;
  17. const string nl = "\n";
  18. const int N = 1e7;
  19.  
  20. void oldsieve() {
  21. vector<bool> prime(N + 1, 1);
  22. vector<int> primes;
  23. prime[0] = prime[1] = 0;
  24. for(int i = 2; i * i <= N; ++i) {
  25. if(prime[i]) {
  26. primes.pb(i);
  27. for(int j = i * i; j <= N; j += i) {
  28. prime[j] = 0;
  29. }
  30. }
  31. }
  32. }
  33.  
  34. void newsieve(int n = N) {
  35. std::vector <int> prime;
  36. bool is_composite[n + 1];
  37. std::fill (is_composite, is_composite + n, false);
  38. for (int i = 2; i < n; ++i) {
  39. if (!is_composite[i]) prime.push_back (i);
  40. for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
  41. is_composite[i * prime[j]] = true;
  42. if (i % prime[j] == 0) break;
  43. }
  44. }
  45. }
  46.  
  47. int32_t main() {
  48. ios::sync_with_stdio(0);
  49. cin.tie(nullptr);
  50.  
  51. auto t = clock();
  52. oldsieve();
  53. auto t1 = clock();
  54. cout << "oldsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
  55. t = clock();
  56. newsieve();
  57. t1 = clock();
  58. cout << "newsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
  59. }
Success #stdin #stdout 0.19s 23560KB
stdin
Standard input is empty
stdout
oldsieve: 0.043665
newsieve: 0.141664