#include <bits/stdc++.h>
const int MAXINT = 2147483640;
const long long MAXLL = 9223372036854775800LL;
const long long MAXN = 1123456;
using namespace std;
bool is_not_prime[MAXN];
vector<long long> primes;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long x, m = 1e6;
  long long ans = MAXLL;
  cin >> x;
  for (long long i = 2; i <= m; ++i)
    if (!is_not_prime[i]) {
      primes.push_back(i);
      for (long long j = i * i; j <= m; j += i) is_not_prime[j] = 1;
    }
  for (long long i = 2; i * i <= x; ++i)
    if (x % i == 0) {
      long long a = i, b = x / i;
      if (!is_not_prime[a]) {
        long long R = x, L = (x / a - 1) * a + 1;
        for (int j = 0; j < primes.size(); ++j) {
          long long R1 = (L / primes[j] + bool(L % primes[j])) * primes[j];
          if (R1 >= L && R1 <= R) {
            if (R1 - primes[j] + 1 <= L && R1 - primes[j] + 1 >= 3)
              ans = min(ans, R1 - primes[j] + 1);
          }
        }
      }
      a = b;
      if (!is_not_prime[a]) {
        long long R = x, L = (x / a - 1) * a + 1;
        for (int j = 0; j < primes.size(); ++j) {
          long long R1 = (L / primes[j] + bool(L % primes[j])) * primes[j];
          if (R1 >= L && R1 <= R) {
            if (R1 - primes[j] + 1 >= 3) ans = min(ans, R1 - primes[j] + 1);
          }
        }
      }
    }
  cout << ans << '\n';
  return 0;
}
