#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 1;
int prime[MAX_N];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; (i) < (MAX_N); ++i) prime[i] = 1;
  prime[0] = prime[1] = 0;
  for (int i = (2); (i) < (MAX_N); ++i) {
    if (prime[i])
      for (int j = 2 * i; j < MAX_N; j += i) prime[j] = 0;
  }
  for (int i = n - 1; i >= 2; i--)
    if (prime[i] && n % i == 0) {
      int k = n - i + 1;
      int ans = k;
      for (int d = (2); (d) < (MAX_N); ++d) {
        if (!prime[d]) continue;
        int l = (k - 1) / d * d;
        if (l != 0 && l + d >= k && l + d <= n) {
          ans = min(ans, l + 1);
        }
      }
      printf("%d\n", ans);
      return 0;
    }
  return 0;
}
