#include <bits/stdc++.h>
using namespace std;
int prime[1000010], cnt;
bool vis[1000010];
int main() {
  for (int i = 2; i <= 1e6; i++) {
    if (!vis[i]) {
      prime[++cnt] = i;
      for (int j = i; j <= 1e6; j += i) vis[j] = 1;
    }
  }
  int x, cnt2, ans = 1e9;
  scanf("%d", &x);
  for (int i = 1; i <= cnt && prime[i] < x; i++) {
    if (x % prime[i] == 0) {
      cnt2 = prime[i];
    }
  }
  int l = x - cnt2 + 1, r = x;
  for (int i = 1; i <= cnt; i++) {
    if (prime[i] >= l) break;
    if (ceil(l * 1.0 / prime[i]) <= floor(r * 1.0 / prime[i])) {
      int w = ceil(l * 1.0 / prime[i]) * prime[i];
      ans = min(ans, w - prime[i] + 1);
    }
  }
  printf("%d\n", ans);
  return 0;
}
