fork download
copy 
  1. // AddPrimeToN.cpp : アプリケーションのエントリ ポイントを定義します。
  2. //
  3.  
  4. #include <iostream>
  5. #include <cstdint>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9.  
  10. typedef std::vector<std::int64_t> DType;
  11.  
  12. //エラトステネスの篩型プライムエンカウンター。
  13.  
  14. template<class T = std::size_t>
  15. class PrimeEncounterAnother {
  16. public:
  17. 	typedef std::vector<bool> PrimeSet;
  18. 	typedef T Integer;
  19.  
  20. 	PrimeEncounterAnother() {
  21. 		Clear();
  22. 	}
  23.  
  24. 	bool Clear() {
  25. 		Primes.clear();
  26. 		if (Primes.size() == 0) {
  27. 			Primes.push_back(true);
  28. 			Primes.push_back(true);
  29. 			Searched = 1;
  30. 		}
  31. 		return true;
  32. 	}
  33.  
  34. 	bool Search(const Integer& N) {
  35. 		if (Searched >= N) return false;
  36. 		Integer L = static_cast<Integer>(std::sqrt(N)) + 1;
  37. 		Primes.resize(N + 1);
  38. 		for (Integer i = 0; i < L; i++) {
  39. 			if (Primes[i] == true) continue;
  40. 			for (Integer j = (Searched / i) + 1; i*j <= N; j++) {
  41. 				if (j <= 1)continue;
  42. 				Primes[i*j] = true;
  43. 			}
  44. 		}
  45. 		Searched = N + 1;
  46. 		return true;
  47. 	}
  48. 	Integer IsSearched() {
  49. 		return Searched;
  50. 	}
  51. 	Integer Size() {
  52. 		return Primes.size();
  53. 	}
  54. 	bool operator [](const Integer& Idx) {
  55. 		return !Primes[Idx];
  56. 	}
  57. protected:
  58. 	PrimeSet Primes;
  59. 	Integer Searched;
  60. };
  61.  
  62. bool Rec(DType P, DType D, const std::uint64_t& A, const std::uint64_t& V,const std::uint64_t& LN,DType& R) {
  63. 	if (D.size() > LN) return false;
  64. 	if (A < V)return false;
  65. 	if (A == V) {
  66. 		R = D;
  67. 		return true;
  68. 	}
  69.  
  70. 	for (std::size_t i = 0; i < P.size(); i++) {
  71. 		D.push_back(P[i]);
  72. 		P.erase(P.begin() + i);
  73. 		Rec(P, D, A, V + D.back(), LN, R);
  74. 		P.insert(P.begin() + i,D.back());
  75. 		D.pop_back();
  76. 	}
  77.  
  78. 	return false;
  79. }
  80.  
  81. DType MakeHoge(std::uint64_t N) {
  82. 	PrimeEncounterAnother<std::uint64_t> P;
  83. 	DType D;
  84. 	P.Search(N);
  85. 	for (std::uint64_t i = 2; i < P.IsSearched(); i++) {
  86. 		if (P[i] == true)D.push_back(i);
  87. 	}
  88.  
  89. 	std::vector<std::vector<std::int64_t>> DP(D.size() + 2);
  90. 	for (auto& o : DP) {
  91. 		o.resize(N + 2);
  92. 	}
  93. 	std::vector<std::vector<std::vector<std::int64_t>>> T(D.size() + 2);
  94. 	for (auto& o : T) {
  95. 		o.resize(N + 2);
  96. 	}
  97. 	for (std::size_t j = 0; j < D.size(); j++) DP[D.size()][j] = 0;
  98.  
  99. 	for (std::int64_t i = D.size() - 1; i >= 0; i--) {
  100. 		for (std::int64_t j = 0; j <= N; j++) {
  101. 			if (j < D[i]) {
  102. 				DP[i][j] = DP[i + 1][j];
  103. 				T[i][j] = T[i + 1][j];
  104. 			}
  105. 			else {
  106. 				if (DP[i + 1][j] > DP[i + 1][j - D[i]] + D[i]) {
  107. 					DP[i][j] = DP[i + 1][j];
  108. 					T[i][j] = T[i + 1][j];
  109. 				}
  110. 				else {
  111. 					DP[i][j] = DP[i + 1][j - D[i]] + D[i];
  112. 					T[i + 1][j - D[i]].push_back(D[i]);
  113. 					T[i][j] = T[i + 1][j - D[i]];
  114. 				}
  115. 			}
  116. 		}
  117. 	}
  118. 		std::vector<std::int64_t> R = T[0][N];
  119. 		std::sort(R.begin(), R.end());
  120.  
  121. 		return R;
  122.  
  123. }
  124.  
  125. int main()
  126. {
  127. 	std::uint64_t N=0;
  128. 	auto R=MakeHoge(2018);
  129. 	std::cout << R.size() << ": " ;
  130. 	for (auto& o: R) {
  131. 		N += o;
  132. 	}
  133. 	std::cout << N<< ": " ;
  134. 	for (auto& o : R) {
  135. 		std::cout << o << ',';
  136. 	}
  137. 	std::cout<<std::endl;
  138.  
  139.     return 0;
  140. }
  141.  
  142.  
Success #stdin #stdout 0.07s 46036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
33: 2018: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,167,
https://ideone.com/XzeJ1E
language:
C++ (gcc 8.3)
created:
6 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!