#include <bits/stdc++.h>
const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};
const int N = (int)1e6 + 228;
using namespace std;
int x;
bool prime[N];
bool check(int pos) {
  int npos = pos;
  for (int i = 2; i < pos; i++) {
    if (!prime[i] && (pos + i - 1) / i * i <= x) {
      npos = max((pos + i - 1) / i * i, npos);
    }
  }
  pos = npos;
  for (int i = 2; i < pos; i++) {
    if (!prime[i] && (pos + i - 1) / i * i == x) return true;
  }
  return false;
}
int main() {
  for (int i = 2; i < N; i++) {
    if (!prime[i]) {
      for (int j = i + i; j < N; j += i) prime[j] = true;
    }
  }
  cin >> x;
  int l = 2, r = x;
  while (l < r - 1) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }
  cout << r << endl;
  return 0;
}
