fork(4) 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.  
  12. 	std::uint64_t GetLastFound(){
  13. 		Prime[2] = true;
  14.  
  15. 		return (*(Prime.rbegin())).first;
  16. 	}
  17.  
  18. 	bool FindNextPrime(){
  19. 		Prime[2] = true;
  20.  
  21. 		std::uint64_t i = GetLastFound() + 1;
  22. 		bool F = true;;
  23.  
  24. 		while (true){
  25. 			F = true;
  26. 			for (auto& o : Prime){
  27. 				if (o.first > ((i / 2)+2)) break;
  28. 				if (i%o.first == 0){
  29. 					F = false;
  30. 					break;
  31. 				}
  32. 			}
  33. 			if (F == true){
  34. 				Prime[i] = true;
  35. 				return true;
  36. 			}
  37. 			i++;
  38. 		}
  39. 	}
  40.  
  41. 	bool FindToCount(std::uint64_t N){
  42. 		while (Prime.size() < N){
  43. 			FindNextPrime();
  44. 		}
  45.  
  46. 		return true;
  47. 	}
  48.  
  49. 	bool IsPrime(std::uint64_t N){
  50.  
  51. 		while (GetLastFound() < N){
  52. 			FindNextPrime();
  53. 		}
  54. 		auto it = Prime.find(N);
  55.  
  56. 		return (it != Prime.end());
  57. 	}
  58.  
  59. }
  60.  
  61. int main(){
  62. 	//bool B = SieveOfEratosthenes::IsPrime(10000);
  63. 	//bool b2 = SieveOfEratosthenes::IsPrime(10007);
  64. 	std::cout << "おぎゃー" << std::endl;
  65. 	//bool b3 = SieveOfEratosthenes::IsPrime(65535);
  66.  
  67. 	auto S=std::chrono::system_clock::now();
  68.  
  69.  
  70. 	SieveOfEratosthenes::FindToCount(10000);
  71.  
  72. 	auto E = std::chrono::system_clock::now();
  73.  
  74. 	auto Eli = std::chrono::duration_cast<std::chrono::milliseconds>(E - S);
  75.  
  76. 	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;//17268ms on my pc.
  77.  
  78. 	return 0;
  79. }
Success #stdin #stdout 0.85s 3696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
おぎゃー
経過時間は852ミリ秒だ！
https://ideone.com/DlZW4s
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!