#include #include #include #include using namespace std;

const int MAX_N = 2000000; // 筛的范围扩大到200万

// 欧拉筛法生成质数表 vector eulerSieve(int n) { vector isPrime(n+1, true); vector primes; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; i++) { if (isPrime[i]) primes.push_back(i); for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) { isPrime[i * primes[j]] = false; if (i % primes[j] == 0) break; } } return primes; }

int main() { int p; cin >> p;

// 特殊处理p=0和负数情况
if (p <= 0) {
    cout << 2 << endl;
    return 0;
}

vector<int> primes = eulerSieve(MAX_N);
long long min_product = LLONG_MAX; // 使用long long防止溢出
long long min_max_factor = LLONG_MAX;

for (int a : primes) {
    // 当a超过p时，后续乘积只会更大，无需继续
    if (a > p) break;
    
    // 计算b的最小需求（向上取整）
    int b0 = (p % a == 0) ? p/a : p/a + 1;
    if (b0 < a) b0 = a; // 保证b≥a
    
    // 在质数表中查找大于等于b0的最小质数
    auto it = lower_bound(primes.begin(), primes.end(), b0);
    if (it == primes.end()) continue;
    int b = *it;
    
    // 计算乘积并检查大小
    long long product = (long long)a * b;
    if (product < min_product) {
        min_product = product;
        min_max_factor = b;
    } else if (product == min_product && b < min_max_factor) {
        min_max_factor = b;
    }
}

cout << min_max_factor << endl;
return 0;

}