#include <bits/stdc++.h>
using namespace std;
long long total;
vector<long long> prime;
bool vis[1001000 + 100];
void seive() {
  prime.push_back(2);
  for (long long i = 3; i <= 1001000; i += 2) {
    if (vis[i]) continue;
    prime.push_back(i);
    for (long long j = i * i; j <= 1001000; j += 2 * i) vis[j] = 1;
  }
}
bool calc(long long val) {
  long long ans;
  for (long long i = 0; prime[i] < val; i++) {
    ans = ceil((val * 1.0) / prime[i]) * prime[i];
    if (ans > total) continue;
    if (ans == total) return true;
  }
  return false;
}
bool step(long long val) {
  long long ans, store = val;
  for (long long i = 0; prime[i] < val; i++) {
    ans = ceil((val * 1.0) / prime[i]) * prime[i];
    if (ans > total) continue;
    store = max(store, ans);
  }
  if (calc(store)) return true;
}
int main() {
  seive();
  scanf("%lld", &total);
  long long lo = 3, hi = total;
  long long mid;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (step(mid))
      hi = mid - 1;
    else
      lo = mid + 1;
  }
  cout << lo << endl;
}
