// AddPrimeToN.cpp : アプリケーションのエントリ ポイントを定義します。
//
#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
#include <algorithm>
typedef std::vector<std::int64_t> DType;
//エラトステネスの篩型プライムエンカウンター。
template<class T = std::size_t>
class PrimeEncounterAnother {
public:
typedef std::vector<bool> PrimeSet;
typedef T Integer;
PrimeEncounterAnother() {
Clear();
}
bool Clear() {
Primes.clear();
if (Primes.size() == 0) {
Primes.push_back(true);
Primes.push_back(true);
Searched = 1;
}
return true;
}
bool Search(const Integer& N) {
if (Searched >= N) return false;
Integer L = static_cast<Integer>(std::sqrt(N)) + 1;
Primes.resize(N + 1);
for (Integer i = 0; i < L; i++) {
if (Primes[i] == true) continue;
for (Integer j = (Searched / i) + 1; i*j <= N; j++) {
if (j <= 1)continue;
Primes[i*j] = true;
}
}
Searched = N + 1;
return true;
}
Integer IsSearched() {
return Searched;
}
Integer Size() {
return Primes.size();
}
bool operator [](const Integer& Idx) {
return !Primes[Idx];
}
protected:
PrimeSet Primes;
Integer Searched;
};
bool Rec(DType P, DType D, const std::uint64_t& A, const std::uint64_t& V,const std::uint64_t& LN,DType& R) {
if (D.size() > LN) return false;
if (A < V)return false;
if (A == V) {
R = D;
return true;
}
for (std::size_t i = 0; i < P.size(); i++) {
D.push_back(P[i]);
P.erase(P.begin() + i);
Rec(P, D, A, V + D.back(), LN, R);
P.insert(P.begin() + i,D.back());
D.pop_back();
}
return false;
}
DType MakeHoge(std::uint64_t N) {
PrimeEncounterAnother<std::uint64_t> P;
DType D;
P.Search(N);
for (std::uint64_t i = 2; i < P.IsSearched(); i++) {
if (P[i] == true)D.push_back(i);
}
std::vector<std::vector<std::int64_t>> DP(D.size() + 2);
for (auto& o : DP) {
o.resize(N + 2);
}
std::vector<std::vector<std::vector<std::int64_t>>> T(D.size() + 2);
for (auto& o : T) {
o.resize(N + 2);
}
for (std::size_t j = 0; j < D.size(); j++) DP[D.size()][j] = 0;
for (std::int64_t i = D.size() - 1; i >= 0; i--) {
for (std::int64_t j = 0; j <= N; j++) {
if (j < D[i]) {
DP[i][j] = DP[i + 1][j];
T[i][j] = T[i + 1][j];
}
else {
if (DP[i + 1][j] > DP[i + 1][j - D[i]] + 1) {
DP[i][j] = DP[i + 1][j];
//T[i][j] = T[i + 1][j];
}
else {
DP[i][j] = DP[i + 1][j - D[i]] + 1;
T[i + 1][j - D[i]].push_back(D[i]);
T[i][j] = T[i + 1][j - D[i]];
}
}
}
}
std::vector<std::int64_t> R = T[0][N];
std::sort(R.begin(), R.end());
return R;
}
int main()
{
std::uint64_t N=0;
auto R=MakeHoge(2018);
std::cout << R.size() << ": " ;
for (auto& o: R) {
N += o;
}
std::cout << N<< ": " ;
for (auto& o : R) {
std::cout << o << ',';
}
std::cout<<std::endl;
return 0;
}