#include <bits/stdc++.h>
using namespace std;
bool isprime(long long int n) {
  if (n < 2) return false;
  for (long long int i = 2; i <= sqrt(n); i++)
    if (n % i == 0) return false;
  return true;
}
long long gcd(long long int a, long long int b) {
  if (a == 0 || b == 0)
    return a + b;
  else
    return gcd(b, a % b);
}
int pr[2000000], lrgprm[1000000], pal[2000000];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  pr[1] = 1;
  for (long long int i = 2; i <= 1000000; i++)
    if (pr[i] == 0)
      for (long long int j = 2 * i; j <= 1000000; j += i) pr[j] = i;
  long long int x2;
  cin >> x2;
  long long int lp = pr[x2], ans = 999999;
  for (long long int j = x2 - lp + 1; j <= x2; j++) {
    long long int tm = pr[j];
    if (j - tm + 1 < 3 || pr[j] == 0) continue;
    ans = min(ans, j - tm + 1);
  }
  cout << ans;
  return 0;
}
