#include <bits/stdc++.h>
using namespace std;
const int maxn = 200050;
int cnt = 0, x2, minn, st, st2, updated_i, updated_j;
int nowsize, unused, tmp;
int a[maxn], b[maxn];
int pre[maxn], suf[maxn], used[maxn];
const int M = 1e6 + 5;
int max_devide[M];
bool mark[M];
int prime[M];
void sieve_prime() {
  for (int i = 0; i < M; i++) {
    max_devide[i] = i;
  }
  memset(mark, true, sizeof(mark));
  mark[0] = mark[1] = false;
  for (int i = 2; i <= M; i++) {
    if (mark[i]) {
      for (int j = i * 2; j < M; j += i) {
        mark[j] = false;
        max_devide[j] = i;
      }
    }
  }
}
int main() {
  cin >> x2;
  int tmp = x2;
  sieve_prime();
  for (int i = 0; i < 1e6 + 5; i++) {
    if (mark[i]) {
      prime[cnt++] = i;
    }
  }
  minn = 0x7fffffff;
  for (int i = cnt - 1; i >= 0; i--) {
    if (tmp % prime[i] != 0) continue;
    st = tmp - prime[i] + 1;
    for (int j = st; j <= tmp; j++) {
      if (j < 3) continue;
      st2 = j - max_devide[j] + 1;
      if (st2 < 3) continue;
      if (st2 < minn) {
        minn = st2;
        updated_i = i;
        updated_j = j;
      }
    }
    break;
  }
  cout << minn << endl;
}
