#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define VEC2(T, N, M) vector(N, vector(M)); #define inf 0x3f3f3f3f3f3f3f3f #define PB push_back #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define SET(a,c) memset(a,c,sizeof a) #define CLR(a) memset(a,0,sizeof a) #define VS vector #define VI vector #define DEBUG(x) cout<<#x<<": "<b?b:a) #define MAX(a,b) (a>b?a:b) #define pi 2*acos(0.0) #define INFILE() freopen("in0.txt","r",stdin) #define OUTFILE()freopen("out0.txt","w",stdout) #define ll long long #define ull unsigned long long #define pii pair #define pcc pair #define pic pair #define pci pair #define eps 1e-14 #define FST first #define SEC second #define SETUP cin.tie(0), ios::sync_with_stdio(false), cout << setprecision(15) << std::fixed; template using vec2 = std::vector>; namespace { struct input_returnner { ll N; input_returnner(ll N_ = 0) :N(N_) {} template operator vector() const { vector res(N); for (auto &a : res) cin >> a; return std::move(res); } template operator T() const { T res; cin >> res; return res; } template T operator - (T right) { return T(input_returnner()) - right; } template T operator + (T right) { return T(input_returnner()) + right; } template T operator * (T right) { return T(input_returnner()) * right; } template T operator / (T right) { return T(input_returnner()) / right; } template T operator << (T right) { return T(input_returnner()) << right; } template T operator >> (T right) { return T(input_returnner()) >> right; } }; template input_returnner in() { return in(); } input_returnner in() { return input_returnner(); } input_returnner in(ll N) { return std::move(input_returnner(N)); } } template istream& operator >> (istream& is, vector& vec) { for (T& x : vec) is >> x; return is; } template < typename T > struct is_vector : std::false_type {}; template < typename T > struct is_vector> : std::true_type {}; template < typename T > constexpr bool is_vector_v = is_vector::value; template std::ostream& operator<< (std::ostream& out, const std::vector& v) { if (!v.empty()) { for (int i = 0; i < v.size(); ++i) { out << v[i] << (i == v.size() - 1 ? "\n" : (is_vector_v ? "" : ", ")); } } return out; } namespace std { // ref: https://stackoverflow.com/questions/7110301/generic-hash-for-tuples-in-unordered-map-unordered-set template inline void hash_combine(std::size_t& seed, T const& v) { seed ^= std::hash()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } // Recursive template code derived from Matthieu M. template ::value - 1> struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { HashValueImpl::apply(seed, tuple); hash_combine(seed, std::get(tuple)); } }; template struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { hash_combine(seed, std::get<0>(tuple)); } }; template struct hash> { size_t operator()(std::tuple const& tt) const { size_t seed = 0; HashValueImpl >::apply(seed, tt); return seed; } }; template class hash> { public: size_t operator()(const std::pair& x) const { return hash>()(std::tie(x.first, x.second)); } }; } // ref: https://stackoverflow.com/questions/6245735/pretty-print-stdtuple namespace aux { template struct seq {}; template struct gen_seq : gen_seq {}; template struct gen_seq<0, Is...> : seq {}; template void print_tuple(std::basic_ostream& os, Tuple const& t, seq) { using swallow = int[]; (void)swallow { 0, (void(os << (Is == 0 ? "" : ", ") << std::get(t)), 0)... }; } } // aux:: template auto operator<<(std::basic_ostream& os, std::tuple const& t) -> std::basic_ostream& { os << "("; aux::print_tuple(os, t, aux::gen_seq()); return os << ")"; } template std::ostream & operator<<(std::ostream & os, const std::pair & p) { return os << "(" << p.first << ", " << p.second << ")"; } // ref: https://stackoverflow.com/questions/8542591/c11-reverse-range-based-for-loo�Fp template struct reversion_wrapper { T& iterable; }; template auto begin(reversion_wrapper w) { return std::rbegin(w.iterable); } template auto end(reversion_wrapper w) { return std::rend(w.iterable); } template reversion_wrapper REV(T&& iterable) { return { iterable }; } ll MOD = 1e9 + 7; class prime; void solve(); signed main() { SETUP; solve(); #ifdef _DEBUG system("pause"); #endif return 0; } #define int ll // template template struct fkvector { public: vector v; fkvector(size_t size) :v(size) {} size_t size() const { return v.size(); } T& operator [] (const int index) { return v[index]; } T dot(const fkvector& right) { assert(v.size() == right.size()); T res = 0; for (int i = 0; i < right.size(); ++i) { res += v[i] * right.v[i]; } return res; } void operator = (const fkvector& right) { v.clear(); v.resize(right.size()); copy(right.v.begin(), right.v.end(), v.begin()); } fkvector operator + (const fkvector& right) { assert(v.size() == right.size()); fkvector res(v.size()); for (size_t i = 0; i < v.size(); ++i) { res[i] = v[i] + right.v[i]; } return res; } fkvector operator - (const fkvector& right) { assert(v.size() == right.size()); fkvector res(v.size()); for (size_t i = 0; i < v.size(); ++i) { res[i] = v[i] - right.v[i]; } return res; } void operator += (const fkvector& right) { assert(v.size() == right.size()); *this = *this + right; } void operator -= (const fkvector& right) { assert(v.size() == right.size()); *this = *this - right; } void print() { cout << "{"; for (int i = 0; i < v.size()-1; ++i) { cout << v[i] << ", "; } cout << v.back(); cout << "}" << endl; } }; template struct fkmat { vector > mat; size_t getRowCount() const { return mat.size(); } size_t getColomnCount() const { return mat[0].size(); } size_t size() const { return mat.size(); } fkmat(size_t size_row,size_t size_colomn):mat(size_row, vector(size_colomn)) {} vector& operator [] (const int index) { return mat[index]; } //Identity matrix fkmat Identity() { for (int i = 0; i < mat.size(); ++i) { mat[i][i] = 1; } return *this; } void operator = (const fkmat& right) { mat.clear(); mat.resize(right.size()); for (int i = 0; i < right.size(); ++i) { mat[i] = right.mat[i]; } } fkmat operator + (const fkmat& right) { fkmat res(getRowCount(), getColomnCount()); for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { res[i][j] = mat[i][j] + right.mat[i][j]; } } return res; } fkmat operator - (const fkmat& right) { fkmat res(getRowCount(), getColomnCount()); for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { res[i][j] = mat[i][j] - right.mat[i][j]; } } return res; } fkmat operator * (const fkmat& right) { fkmat res(getRowCount(), getColomnCount()); assert(getColomnCount() == right.getRowCount()); for (int r = 0; r < getRowCount(); ++r) { for (int c = 0; c < right.getColomnCount(); ++c) { for (int k = 0; k < getColomnCount(); ++k) { res[r][c] += mat[r][k] * right.mat[k][c]; res[r][c] %= MOD; } } } return res; } void operator += (const fkmat& right) { for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { mat[i][j] += right.mat[i][j]; } } } void operator -= (const fkmat& right) { for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { mat[i][j] -= right.mat[i][j]; } } } void operator *= (const fkmat& right) { *this = *this * right; } //power n void pow(long long n, fkmat* dst) { dst->Identity(); fkmat x(getRowCount(), getColomnCount()); x.mat = mat; while (n > 0) { if (n & 1) *dst = *dst * x; x *= x; x %= MOD; n >>= 1; } } //power n void pow(long long n) { fkmat res(getRowCount(), getColomnCount()); res = fkmat(getRowCount(), getColomnCount()).Identity(); fkmat x(getRowCount(), getColomnCount()); x = *this; while (n > 0) { if (n & 1) res = res * x; x *= x; n >>= 1; } *this = res; } void print() { for (size_t i = 0; i < mat.size(); ++i) { for (size_t j = 0; j < mat[i].size(); ++j) { cout << mat[i][j] << " "; } cout << endl; } } }; int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; } class prime { private: public: std::vector primes; std::vector isPrime; prime(int num = 0) { if (num == 0) return; isPrime.resize(num + 1); fill(isPrime.begin(), isPrime.end(), true); int ma = sqrt(num) + 1; isPrime[0] = isPrime[1] = false; int cnt = 0; for (int i = 2; i <= ma; ++i) if (isPrime[i]) { for (int j = 2; i*j <= num; ++j) { isPrime[i*j] = false; cnt++; } } primes.reserve(cnt); for (int i = 0; i GetFactor(int num) { std::map res; int ma = sqrt(num) + 1; int a = 2; auto it = primes.begin(); while (num >= a*a) { if (num%a == 0) { res[a]++; num /= a; } else { if (it == primes.end()) ++a; else { ++it; a = *it; } } } res[num]++; return res; } }; map, int> memo; // {depth, mask} = res; int f(vector >& dps, int depth, int mask) { if (depth == 0) return dps[0][mask]; if (memo.find({ depth, mask }) != memo.end()) return memo[{depth, mask}]; int res = 0; for(int i = 0;;i = (i-mask) & mask){ // take out i res = max(res, f(dps, depth - 1, mask - i) + dps[depth][i]); if (i == mask) break; } memo[{depth, mask}] = res; return res; } void solve() { int N; cin >> N; prime primes(sqrt(N)+1); unordered_map prime2Num; { prime tempPrime(N + 1); REP(i, tempPrime.primes.size()) { prime2Num[tempPrime.primes[i]] = i; } } int M = primes.primes.size(); int res = 0; vector > dps(prime2Num.size() - M+1 , vector(1 << M)); FOR(i, 2, N+1) { auto factors = primes.GetFactor(i); int bits = 0; int maxFactor = 0; for (auto &p : factors) { maxFactor = max(p.first, maxFactor); if(p.first <= primes.primes.back()){ bits += (1 << prime2Num[p.first]); } } if (maxFactor <= primes.primes.back()) { dps[0][bits] = max(dps[0][bits], i); } else { int num = prime2Num[maxFactor] - primes.primes.size(); dps[num+1][bits] = max(dps[num][bits], i); } } { vector& dp = dps[0]; FOR(tar, 1, dp.size()) { for(int i = 0;;i = (i-tar) & tar){ int invI = tar - i; dp[tar] = max(dp[tar], dp[i]+dp[invI]); if (i == tar) break; } } } cout << f(dps, dps.size() - 1, (1 << M) - 1) << endl; }