#include <bits/stdc++.h>
using namespace std;
int n, big[1000005];
int prime[1000005];
bitset<1000005> is;
int cnt = 0;
inline void work(int n) {
  is[0] = is[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (is[i] == 0) {
      big[i] = i;
      prime[++cnt] = i;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
      is[i * prime[j]] = 1;
      big[i * prime[j]] = big[i];
      if ((i % prime[j]) == 0) {
        break;
      }
    }
  }
}
int main() {
  cin >> n;
  work(n);
  int ans = 10000000;
  for (int i = n - big[n] + 1; i <= n; i++) {
    if (is[i]) {
      ans = min(ans, i - big[i] + 1);
    }
  }
  cout << ans;
  return 0;
}
