#include <bits/stdc++.h>
using namespace std;
vector<vector<long long int> > adj(1000005);
long long int vis[1000005];
vector<bool> prime(1000005, true);
vector<long long int> v(1000003, 1);
void pre() {
  for (int i = 2; i < 1000005; i++) {
    if (prime[i] == false) continue;
    for (int j = 2 * i; j < 1000005; j += i) {
      prime[j] = false;
      v[j] = i;
    }
  }
}
struct comp {
  bool operator()(pair<long long int, long long int> p1,
                  pair<long long int, long long int> p2) {
    if (p1.second == p2.second) return p1.first > p2.first;
    return p1.second < p2.second;
  }
};
long long int mini = 1e18, cnt = 0;
map<pair<long long int, long long int>, long long int> dir;
vector<long long int> c(300005, 1e18);
void dfs(long long int v, long long int d) {
  vis[v] = 1;
  c[v] = d;
  mini = min(mini, c[v]);
  for (auto x : adj[v]) {
    if (!vis[x]) {
      if (dir.count({v, x}) == 0) {
        cnt++;
        dfs(x, d - 1);
      } else
        dfs(x, d + 1);
    }
  }
}
int p2[300005];
long long int power(long long int x, long long int y) {
  if (y == 0)
    return 1;
  else if (y % 2 == 0)
    return power(x, y / 2) * power(x, y / 2);
  else
    return x * power(x, y / 2) * power(x, y / 2);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int q = 1;
  while (q--) {
    long long int n, i, ans = 1e18;
    pre();
    cin >> n;
    for (i = n - v[n] + 1; i < n; i++) {
      if (ans >= 3) ans = min(ans, i - v[i] + 1);
    }
    cout << ans;
  }
}
