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::uint64_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. std::int64_t MakeHoge(std::uint64_t N) {
  63. 	PrimeEncounterAnother<std::uint64_t> P;
  64. 	DType D;
  65. 	P.Search(N);
  66. 	for (std::uint64_t i = 2; i < P.IsSearched(); i++) {
  67. 		if (P[i] == true)D.push_back(i);
  68. 	}
  69.  
  70. 	std::vector<std::vector<std::int64_t>> DP(D.size()+2);
  71. 	for (auto& o : DP) {
  72. 		o.resize(N+2);
  73. 	}
  74.  
  75. 	for (std::size_t j = 0; j < D.size(); j++) DP[D.size()][j] = 0;
  76.  
  77. 	for (std::int64_t i = D.size()-1; i >= 0; i--) {
  78. 		for (std::int64_t j = 0; j <= N; j++) {
  79. 			if (j < D[i]) {
  80. 				DP[i][j] = DP[i + 1][j];
  81. 			}
  82. 			else {
  83. 				DP[i][j] = std::max(DP[i + 1][j], DP[i + 1][j - D[i]] + 1);
  84. 			}
  85. 		}
  86. 	}
  87.  
  88.  
  89. 	return DP[0][N];
  90. }
  91.  
  92. int main()
  93. {
  94. 	std::int64_t R;
  95. 	R=MakeHoge(2018);
  96. 	std::cout << R << std::endl;
  97.  
  98.     return 0;
  99. }
  100.  
  101.  
Success #stdin #stdout 0.01s 7512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
33
https://ideone.com/lwcNQR
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!