#include <bits/stdc++.h>
using namespace std;
template <class T>
int size(const T &x) {
  return x.size();
}
const int INF = ~(1 << 31);
const double pi = acos(-1);
const double EPS = 1e-9;
bool isprime(int n) {
  if (n == 1) return false;
  if (n == 2) return true;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
vector<int> factors(int n) {
  vector<int> ans;
  int z = 2;
  while (z * z <= n) {
    if (n % z == 0) {
      ans.push_back(z);
      n /= z;
    } else
      z++;
  }
  if (n > 1) ans.push_back(n);
  return ans;
}
int main() {
  cin.sync_with_stdio(false);
  long long x1;
  cin >> x1;
  long long mx = x1;
  if (isprime(x1)) {
    cout << x1 << endl;
    return 0;
  }
  for (int i = x1; i >= 0; i--) {
    if (x1 % i == 0 && isprime(i)) {
      int ans = INF;
      for (int j = x1; j > x1 - i; j--) {
        vector<int> facts = factors(j);
        for (auto it = (facts).begin(); it != (facts).end(); ++it) {
          if (*it == j) continue;
          ans = min(ans, j - *it + 1);
        }
      }
      cout << ans << endl;
      break;
    }
  }
  return 0;
}
