#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int M = 59100;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
int n, m;
int cal(int x) {
  int now = x, ans = 1;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      ans = i;
      while (x % i == 0) x /= i;
    }
  }
  if (x != now) ans = max(ans, x);
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  int down = n - cal(n) + 1;
  int ans = inf;
  for (int i = down; i <= n; i++) ans = min(ans, i - cal(i) + 1);
  printf("%d\n", ans);
  return 0;
}
