#include <bits/stdc++.h>
using namespace std;
long long int powll(long long int n, long long int p) {
  if (p == 0)
    return 1;
  else if (p == 1)
    return n;
  else {
    long long int ans = powll(n, p / 2);
    ans = ans * ans;
    if (p % 2 == 1) ans = ans * n;
    return ans;
  }
}
vector<long long int> factlist(long long int n) {
  if (n < 0)
    return {};
  else {
    vector<long long int> ret((int)n + 1);
    ret[0] = 1;
    for (int i = 1; i <= (int)(int)n; i++) ret[i] = ret[i - 1] * i;
    return ret;
  }
}
vector<vector<long long int>> combinationlist(int n) {
  vector<vector<long long int>> ret(n, vector<long long int>(n, 1));
  for (int i = 1; i <= (int)n - 1; i++) {
    for (int j = 1; j <= (int)i - 1; j++) {
      ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
    }
  }
  return ret;
}
long long int ceil_div(long long int a, long long int b) {
  if (a % b == 0)
    return a / b;
  else
    return a / b + 1;
}
void printv(vector<long long int> a) {
  for (int i = 0; i < (int)a.size(); i++) cout << a[i] << endl;
  cout << endl;
}
void printmx(vector<vector<long long int>> A) {
  for (int i = 0; i < (int)A.size(); i++) {
    for (int j = 0; j < (int)A[0].size(); j++) {
      cout << A[i][j] << " ";
    }
    cout << endl;
  }
  cout << endl;
}
vector<long long int> loop_vec_accumulate(vector<long long int> a,
                                          long long int length) {
  int n = a.size();
  vector<long long int> ret(n, 0);
  if (n == 0) return ret;
  long long int p = length / n;
  if (p > 0) {
    for (int i = 0; i < (int)n; i++) ret[0] += a[i];
    ret[0] *= p;
  }
  for (int i = 0; i < (int)length % n; i++) ret[0] += a[i];
  for (int i = 1; i <= (int)n - 1; i++) {
    ret[i] = ret[i - 1] - a[i - 1] + a[(i + length - 1) % n];
  }
  return ret;
}
vector<vector<long long int>> loop_mx_accumulate(
    vector<vector<long long int>> A, long long int i_length,
    long long int j_length) {
  int m = A.size();
  int n = A[0].size();
  for (int i = 0; i < (int)m; i++) A[i] = loop_vec_accumulate(A[i], j_length);
  vector<vector<long long int>> trans_A(n, vector<long long int>(m, 0));
  for (int i = 0; i < (int)n; i++) {
    for (int j = 0; j < (int)m; j++) trans_A[i][j] = A[j][i];
  }
  for (int i = 0; i < (int)n; i++)
    trans_A[i] = loop_vec_accumulate(trans_A[i], i_length);
  for (int i = 0; i < (int)m; i++) {
    for (int j = 0; j < (int)n; j++) A[i][j] = trans_A[j][i];
  }
  return A;
}
vector<long long int> divisors(long long int x) {
  vector<long long int> ret;
  for (int i = 1; i <= (int)x; i++) {
    long long int y = (long long int)i * i;
    if (y >= x) {
      if (y == x) ret.push_back(i);
      break;
    } else {
      if (x % i == 0) {
        ret.push_back(i);
        ret.push_back(x / i);
      }
    }
  }
  return ret;
}
vector<int> list_prime_until(int n) {
  vector<int> ret;
  for (int i = 1; i <= (int)n; i++) {
    if (i == 1)
      continue;
    else if (i == 2)
      ret.push_back(2);
    else {
      bool judge = true;
      for (int j = 0; j < (int)ret.size(); j++) {
        if (i % ret[j] == 0) {
          judge = false;
          break;
        }
      }
      if (judge) ret.push_back(i);
    }
  }
  return ret;
}
vector<pair<int, int>> prime_factorize(int n, vector<int> prime_list = {}) {
  vector<pair<int, int>> ret;
  if (prime_list.empty())
    prime_list = list_prime_until(
        (long long int)((double)sqrt(n) + ((sqrt(n) >= 0) ? 0.5 : -0.5)));
  for (int i = 0; i < (int)prime_list.size(); i++) {
    while (n % prime_list[i] == 0) {
      if (ret.size() == 0 || ret.back().first != prime_list[i]) {
        ret.push_back({prime_list[i], 0});
      }
      ret.back().second++;
      n /= prime_list[i];
    }
  }
  if (n != 1) ret.push_back({n, 1});
  return ret;
}
int main() {
  int n;
  cin >> n;
  vector<int> primes = list_prime_until(1e3);
  vector<pair<int, int>> pf = prime_factorize(n, primes);
  int m = (n == pf.back().first) ? n : n - pf.back().first + 1;
  int ans = m;
  for (int k = m; k <= n; k++) {
    vector<pair<int, int>> pf2 = prime_factorize(k, primes);
    ans = min(ans, (k == pf2.back().first) ? k : k - pf2.back().first + 1);
  }
  cout << ans << endl;
}
