fork download
copy 
  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 = 1e8;
  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 2.29s 183048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
oldsieve: 0.690002
newsieve: 1.5946
https://ideone.com/MfaJCF
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!