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. 	int n = N;
  22. 	vector<char> is_prime(n+1, true);
  23. 	is_prime[0] = is_prime[1] = false;
  24. 	for (int i = 2; i <= n; i++) {
  25. 		if (is_prime[i] && i * i <= n) {
  26. 			for (int j = i * i; j <= n; j += i)
  27. 				is_prime[j] = false;
  28. 		}
  29. 	}
  30. }
  31.  
  32. void newsieve(int n = N) {
  33. 	//int prime[n], is_composite[n + 1];
  34. 	std::vector <int> prime(n);
  35. 	vector<bool> is_composite(n + 1, 0);
  36. 	int cnt = 0;
  37. 	for (int i = 2; i < n; ++i) {
  38. 		if(!is_composite[i]) {
  39. 			prime[cnt++] = i;
  40. 		}
  41. 		for (int j = 0; j < cnt && i * prime[j] < n; ++j) {
  42. 			is_composite[i * prime[j]] = true;
  43. 			if (i % prime[j] == 0) break;
  44. 		}
  45. 	}
  46.  
  47. }
  48.  
  49. void newsieve1(int maxN = N) {
  50. 	int pc = 0;
  51. 	//, f[maxN], primes[maxN / 10];
  52. 	vector<int> f(maxN), primes(maxN / 10);
  53. 	for(int i = 2; i < maxN; ++i) {
  54. 		if(!f[i]) {
  55. 			primes[pc++] = i, f[i] = i;
  56. 		}
  57. 		for(int j = 0; j < pc && 1LL * i * primes[j] < maxN && primes[j] <= f[i]; ++j) {
  58. 			f[i * primes[j]] = primes[j];
  59. 		}
  60. 	}
  61. }
  62.  
  63. int32_t main() {
  64. 	ios::sync_with_stdio(0);
  65. 	cin.tie(nullptr);
  66.  
  67. 	auto t = clock();
  68. 	oldsieve();
  69. 	auto t1 = clock();
  70. 	cout << "oldsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
  71. 	t = clock();
  72. 	newsieve1();
  73. 	t1 = clock();
  74. 	cout << "newsieve: " << (1.0 * (t1 - t)) / CLOCKS_PER_SEC << nl;
  75. }
  76.  
Success #stdin #stdout 2.31s 862872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
oldsieve: 1.16819
newsieve: 1.13676
https://ideone.com/N70vwb
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!