#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 2e5 + 7;
const int mxN = 1e6 + 7;
const int eps = -1e9;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
bool isPrime(long long n) {
  if (n < 2) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i += 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long powOfn(long long b, long long p) {
  if (p == 0) return 1;
  long long sq = powOfn(b, p / 2);
  sq *= sq;
  if (p & 1) sq *= b;
  return sq;
}
long long ncr(long long n, long long r) {
  if (n <= 0) return 0;
  long long ans = 1;
  if (n - r < r) r = n - r;
  for (long long i = 0; i < r; i++) {
    ans *= n - i;
    ans /= i + 1;
  }
  return ans;
}
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
vector<int> prime(mxN, 0);
int main() {
  ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
  int x;
  cin >> x;
  for (int i = 2; i <= x; i++) {
    if (!prime[i]) {
      for (int j = i * 2; j <= x; j += i) prime[j] = i;
    }
  }
  int ans = INT_MAX;
  for (int i = x - prime[x] + 1; i <= x; i++) {
    if (!prime[i]) continue;
    ans = min(ans, i - prime[i] + 1);
  }
  cout << ans << endl;
  return 0;
}
