#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  int x2;
  cin >> x2;
  int n = 1000000;
  vector<bool> primes(n + 1, true);
  primes[0] = primes[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (primes[i])
      for (int j = i * i; j <= n; j += i) primes[j] = false;
  }
  int maxip1 = -1;
  for (int p1 = 2; p1 * p1 <= x2; p1++) {
    if (x2 % p1 != 0) continue;
    if (primes[p1]) {
      maxip1 = max(p1, maxip1);
    }
    if (primes[x2 / p1]) {
      maxip1 = max(x2 / p1, maxip1);
      break;
    }
  }
  int ans = n;
  for (int x1 = x2 - maxip1 + 1; x1 <= x2; x1++) {
    for (int p0 = 2; p0 * p0 <= x1; p0++) {
      if (x1 % p0 != 0) continue;
      if (primes[p0]) {
        ans = min(ans, x1 - p0);
      }
      if (primes[x1 / p0]) {
        ans = min(ans, x1 - x1 / p0);
        break;
      }
    }
  }
  cout << ans + 1;
}
