#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
vector<int> pr[N];
bool notprime[N];
vector<int> primes;
int lw[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int x2;
  cin >> x2;
  notprime[0] = 1;
  notprime[1] = 1;
  for (int i = 2; i < N; i++) {
    if (notprime[i]) continue;
    for (int j = i + i; j < N; j += i) notprime[j] = 1;
  }
  for (int i = 0; i < N; i++) {
    if (!notprime[i]) primes.push_back(i);
  }
  for (int i = 0; i < primes.size(); i++) {
    for (int j = primes[i]; j < N; j += primes[i])
      lw[j] = max(lw[j], primes[i]);
  }
  for (int i = 0; i < N; i++) {
    lw[i] = i - lw[i] + 1;
  }
  int ans = INT_MAX;
  for (int i = 0; i < primes.size(); i++) {
    if (x2 % primes[i] == 0) {
      for (int j = x2; j > x2 - primes[i]; j--) {
        if (notprime[j]) ans = min(ans, lw[j]);
      }
    }
  }
  cout << ans;
  return 0;
}
