#include using namespace std; int count(int n) { int v = sqrt(n); vector smalls(v + 1), larges(v + 1); for (int i = 1; i <= v; ++i) { smalls[i] = i - 1; } for (int i = 1; i <= v; ++i) { larges[i] = n / i - 1; } for (int p = 2; p <= v; ++p) { if (smalls[p] == smalls[p - 1]) { continue; } int c = smalls[p - 1]; int w = v / p; int q = p * p; int e = min(n / q, v); int m = n / p; for (int i = 1; i <= w; ++i) { larges[i] -= larges[i * p] - c; } for (int i = w + 1; i <= e; ++i) { larges[i] -= smalls[m / i] - c; } for (int i = v; i >= q; --i) { smalls[i] -= smalls[i / p] - c; } } int ret = smalls[(int) cbrt(n)]; for (int p = 2; p <= v; ++p) { if (smalls[p] != smalls[p - 1]) { ret += larges[p] - smalls[p]; } } return ret; } int main() { int n; scanf("%d", &n); int lo = 0, hi = 1e8; while (hi - lo > 1) { int mi = (lo + hi) >> 1; if (count(mi) >= n) { hi = mi; } else { lo = mi; } } printf("%d\n", hi); return 0; }