fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <cstdint>
  4. #include <chrono>
  5.  
  6. namespace SieveOfEratosthenes{//追記型エラトステネスの篩
  7.  
  8. 	//えーっと、Prime[2]=trueだけはどうやっても導き方がわからんのでハードコーディングで死守している。
  9.  
  10. 	static std::map < std::uint64_t, bool> Prime;
  11. 	static bool IsInit = false;
  12.  
  13. #define ISDANGOMETHOD 1
  14.  
  15. 	std::uint64_t GetLastFound(){
  16. 		if (IsInit == false){
  17. 			Prime[2] = true;
  18. 			Prime[3] = true;
  19. 			IsInit = true;
  20. 		}
  21.  
  22. 		return (*(Prime.rbegin())).first;
  23. 	}
  24.  
  25. 	bool FindNextPrime(){
  26. 		if (IsInit == false){
  27. 			Prime[2] = true;
  28. 			Prime[3] = true;
  29. 			IsInit = true;
  30. 		}	
  31.  
  32. 		std::uint64_t i = GetLastFound() + 1;
  33. 		bool F = true;
  34.  
  35.  
  36.  
  37. #if ISDANGOMETHOD
  38. 		int sub[2] = { -1, 1 };
  39. 		static int C = 0;
  40. 		static int j = 1;
  41. 		i = 6*j + sub[C++];
  42. 		if (C == 2){
  43. 			C = 0;
  44. 			j++;
  45. 		}
  46. #endif
  47.  
  48. 		while (true){
  49. 			F = true;
  50. 			for (auto& o : Prime){
  51. 				if (o.first > ((i / 2)+2)) break;
  52. 				if (i%o.first == 0){
  53. 					F = false;
  54. 					break;
  55. 				}
  56. 			}
  57. 			if (F == true){
  58. 				Prime[i] = true;
  59. 				return true;
  60. 			}
  61. #if ISDANGOMETHOD
  62. 		i = 6*j + sub[C++];
  63. 		if (C == 2){
  64. 			C = 0;
  65. 			j++;
  66. 		}
  67. 			//goto L;
  68. #else
  69. 			i++;
  70. #endif
  71. 		}
  72. 	}
  73. 	bool Clear(){
  74. 		Prime.clear();
  75. 		return true;
  76. 	}
  77. 	bool FindToCount(std::uint64_t N){
  78. 		while (Prime.size() < N){
  79. 			FindNextPrime();
  80. 		}
  81.  
  82. 		return true;
  83. 	}
  84.  
  85. 	bool IsPrime(std::uint64_t N){
  86.  
  87. 		while (GetLastFound() < N){
  88. 			FindNextPrime();
  89. 		}
  90. 		auto it = Prime.find(N);
  91.  
  92. 		return (it != Prime.end());
  93. 	}
  94.  
  95. }
  96.  
  97. int main(){
  98. 	//bool B = SieveOfEratosthenes::IsPrime(10000);
  99. 	//bool b2 = SieveOfEratosthenes::IsPrime(10007);
  100. 	std::cout << "おぎゃー" << std::endl;
  101.  
  102.  
  103. 	auto S=std::chrono::system_clock::now();
  104.  
  105. 	//bool b3 = SieveOfEratosthenes::IsPrime(65535);
  106. 	SieveOfEratosthenes::FindToCount(10000);
  107.  
  108. 	auto E = std::chrono::system_clock::now();
  109.  
  110. 	auto Eli = std::chrono::duration_cast<std::chrono::milliseconds>(E - S);
  111.  
  112. 	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;//17268ms on my pc.
  113.  
  114. 	return 0;
  115. }
Success #stdin #stdout 0.85s 3696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
おぎゃー
経過時間は850ミリ秒だ！
https://ideone.com/UegGZY
language:
C++14 (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!