#include #include #include using namespace std; int n; int dp[500][1<<11]; vector primes; vector> numbers; int dfs(int id, int used) { if (id >= primes.size()) { return 0; } if (dp[id][used] >= 0) { return dp[id][used]; } int ret = dfs(id + 1, used); for (int i = 0; i < numbers[id].size(); i++) { int j; for (j = 0; j < min(id, 11); j++) { if (numbers[id][i] % primes[j] == 0 && (used >> j) % 2 == 1) { break; } } if (j == min(id, 11)) { int newUsed = used; for (j = 0; j < min(id + 1, 11); j++) { if (numbers[id][i] % primes[j] == 0) { newUsed |= (1 << j); } } ret = max(ret, numbers[id][i] + dfs(id + 1, newUsed)); } } return (dp[id][used] = ret); } int main() { int i, j; cin >> n; for (i = 2; i <= n; i++) { for (j = 2; j < i; j++) { if (i % j == 0) { break; } } if (j == i) { primes.push_back(i); } } numbers.resize(primes.size()); for (i = 2; i <= n; i++) { for (j = (int)primes.size() - 1; j >= 0; j--) { if (i % primes[j] == 0) { break; } } numbers[j].push_back(i); } for (i = 0; i < primes.size(); i++) { for (j = 0; j < 2048; j++) { dp[i][j] = -1; } } cout << dfs(0, 0) << endl; return 0; }