#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const int N = 2100000;
const int mod = 1e9 + 7;
int arr[N];
vector<int> xiao;
int main() {
  ios::sync_with_stdio(false);
  for (int i = 2; i <= 1000000; i++) {
    if (arr[i] != 0) continue;
    for (int j = 2; i * j <= 1000000; j++) arr[i * j] = i;
  }
  int n;
  cin >> n;
  int dis = arr[n];
  int ans = inf;
  for (int i = n - dis + 1; i <= n; i++) ans = min(ans, i - arr[i] + 1);
  printf("%d\n", ans);
  return 0;
}
