//================================= // Created on: 2018/07/28 01:03:56 //================================= #include #define show(x) std::cerr << #x << " = " << x << std::endl int main() { constexpr int NUM = 11; constexpr int MAX = 1 << NUM; constexpr int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; int N; std::cin >> N; std::vector mask(N + 1, 0), maxp(N + 1, 0); for (int i = 2, cnt = 0; i <= N; i++) { if (maxp[i] != 0) { continue; } if (cnt < NUM) { mask[i] |= (1 << cnt); } for (int j = 2; i * j <= N; j++) { mask[i * j] |= (cnt < NUM ? (1 << cnt) : 0), maxp[i * j] = i; } cnt++; } std::vector large(MAX, 0); for (int ps = 0; ps < NUM; ps++) { std::vector used(N + 1, false); for (int i = N; i >= 2; i--) { if (maxp[i] <= 31 or used[maxp[i]]) { continue; } bool ok = true; for (int j = 0; j < NUM; j++) { if (((ps & (1 << j)) > 0) and i % p[j] == 0) { ok = false; break; } } if (ok) { large[ps] += i, used[maxp[i]] = true; } } } constexpr int INF = 1 << 30; std::vector dp(MAX, -INF); dp[0] = 0; for (int i = 2; i <= N; i++) { if (maxp[i] > 31) { continue; } for (int j = MAX - 1; j >= 0; j--) { if (dp[j] == -INF or (j & mask[i]) > 0) { continue; } dp[j | mask[i]] = std::max(dp[j | mask[i]], dp[j] + i); } } int ans = 0; for (int i = 0; i < MAX; i++) { ans = std::max(ans, dp[i] + large[i]); } std::cout << ans << std::endl; return 0; }