fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <math.h>
  10. #include <ctime>
  11. #include <memory.h>
  12.  
  13. using namespace std;
  14.  
  15. #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
  16.  
  17. typedef long long LL;
  18. typedef vector<int> vi;
  19.  
  20. const int M = 30000;
  21. const int N = M * M;
  22.  
  23. int Simple()
  24. {
  25. 	vector<unsigned> a(N / 32 + (N % 32 != 0), 0xFFffFFff);
  26. 	for (int i = 2; i * i < N; ++i)
  27. 		if (a[i >> 5] & (1 << (i & 31)))
  28. 			for (int j = i * i; j < N; j += i)
  29. 				a[j >> 5] &= ~(1 << (j & 31));
  30. 	int cnt = 0;
  31. 	for (int i = 2; i < N; ++i)
  32. 		if (a[i >> 5] & (1 << (i & 31)))
  33. 			++cnt;
  34. 	return cnt;
  35. }
  36.  
  37. int Another()
  38. {
  39. 	const int K = 1 << 16;
  40. 	vector<int> _a(K);
  41. 	int* a = &_a[0];
  42.  
  43. 	FOR(i, K)
  44. 		a[i] = 1;
  45. 	vi p;
  46. 	vi pos;
  47. 	for (int i = 2; i * i < M; ++i)
  48. 		if (a[i])
  49. 		{
  50. 			for (int j = i * i; j < M; j += i)
  51. 				a[j] = 0;
  52. 		}
  53. 	for (int i = 2; i < M; ++i)
  54. 		if (a[i])
  55. 		{
  56. 			p.push_back(i);
  57. 			pos.push_back(i * i);
  58. 		}
  59.  
  60. 	int res = 0;
  61. 	int L = 2;
  62. 	while (L < N)
  63. 	{
  64. 		a = &_a[0] - L;
  65.  
  66. 		int R = L;
  67. 		FOR(i, K)
  68. 		{
  69. 			a[R] = 1;
  70. 			++R;
  71. 		}
  72. 		FOR(i, p.size())
  73. 		{
  74. 			int x = pos[i];
  75. 			while (x < R)
  76. 			{
  77. 				a[x] = 0;
  78. 				x += p[i];
  79. 			}
  80. 			pos[i] = x;
  81. 		}
  82. 		FOR(i, K)
  83. 		{
  84. 			if (L < N)
  85. 				res += a[L];
  86. 			++L;
  87. 		}
  88. 	}
  89. 	return res;
  90. }
  91.  
  92. int main()
  93. {
  94. 	{
  95. 		time_t tm = clock();
  96. 		cout << Another() << "\n";
  97. 		cout << (clock() - tm) / (double)CLOCKS_PER_SEC << "\n";
  98. 	}
  99. 	{
  100. 		time_t tm = clock();
  101. 		cout << Simple() << "\n";
  102. 		cout << (clock() - tm) / (double)CLOCKS_PER_SEC << "\n";
  103. 	}
  104.  
  105.  
  106. 	return 0;
  107. }
Time limit exceeded #stdin #stdout 5s 3732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ho83b3
language:
C++ (gcc 8.3)
created:
10 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!