#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
const int inf = INT_MAX;
const long long inff = 1e18;
const long long mod = 1e9 + 7;
long long p[1000007];
long long a[1000007];
long long n;
long long last[maxn];
vector<long long> pp;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (long long i = 2; i <= 1000000; i++) {
    if (!p[i]) {
      pp.push_back(i);
      for (long long j = i * 1ll * i; j <= 1000000; j += i) {
        p[j] = 1;
      }
    }
  }
  for (long long i = 2; i <= 1000000; i++) {
    long long ret, ii = i;
    for (long long j : pp) {
      if (j * 1ll * j > ii) break;
      if (ii % j == 0) {
        ret = j;
        while (ii % j == 0) ii /= j;
      }
    }
    if (ii > 1) ret = ii;
    if (ret == i)
      a[i] = i;
    else
      a[i] = i - ret + 1;
  }
  cin >> n;
  long long ans = inf;
  for (long long i = a[n]; i <= n; i++) {
    ans = min(ans, a[i]);
  }
  cout << ans << endl;
}
