#include <bits/stdc++.h>
using namespace std;
int largest_prime(int n) {
  int max = -1;
  while (n % 2 == 0) {
    max = 2;
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i += 2) {
    while (n % i == 0) {
      max = i;
      n = n / i;
    }
  }
  if (n > 2) {
    max = n;
  }
  return max;
}
bool prime(int n) {
  int i = 2;
  while (i * i <= n) {
    if (n % i == 0) {
      return false;
    }
    i++;
  }
  return true;
}
int main() {
  int n;
  cin >> n;
  int p;
  int temp = n;
  p = largest_prime(temp);
  int ans = INT_MAX;
  for (int i = n - p + 1; i <= n; i++) {
    if (!prime(i)) {
      int q = largest_prime(i);
      if (ans > i - q + 1) {
        ans = i - q + 1;
      }
    }
  }
  cout << ans;
}
