#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
bool notprime[1000001] = {0};
const int N = 78497;
int main() {
  for (int i = 2; i <= 1000000; i++) {
    if (!notprime[i]) {
      prime.push_back(i);
      for (int j = 2 * i; j <= 1000000; j += i) notprime[j] = true;
    }
  }
  int x;
  cin >> x;
  int idx = N;
  while (x % prime[idx] != 0) idx--;
  int p = prime[idx];
  int low = x - p + 1;
  int minn = 10000000;
  for (int i = 0; i < N; i++) {
    int q = prime[i];
    int k = (low / q) * q;
    if (k < low) k += q;
    if ((k <= x) && (k != q)) {
      if (k - q + 1 < minn) {
        minn = k - q + 1;
      }
    }
  }
  cout << max(minn, 3);
}
