#include <bits/stdc++.h>
using namespace std;
const double PI = 3.14159265358979;
const double eps = 1e-6;
const long long _INF = 1e18;
const int INF = 1e9;
const int maxn = 1000010;
const int maxm = 200000;
int tot;
long long primes[maxn], n, ans;
long long vis[maxn];
void ini() {
  tot = 0;
  memset(vis, 0, sizeof(vis));
  for (long long i = 2; i < maxn; ++i)
    if (!vis[i]) {
      primes[tot++] = i;
      for (long long j = i * 2; j < maxn; j += i) vis[j] = i;
    }
}
int main() {
  ini();
  while (~scanf("%I64d", &n)) {
    ans = _INF;
    for (long long i = n - vis[n] + 1; i <= n; ++i)
      ans = min(ans, i - vis[i] + 1);
    printf("%I64d\n", ans);
  }
  return 0;
}
