#include <bits/stdc++.h>
using namespace std;
const int maxN = 1000006;
int primeArray[maxN];
void getPrime() {
  int n = 2;
  while (n < maxN) {
    int num = n * 2;
    while (num < maxN) {
      primeArray[num] = n;
      num += n;
    }
    num = n + 1;
    while (primeArray[num] != 0 && num < maxN) {
      num++;
    }
    n = num;
  }
}
int main() {
  getPrime();
  int x0, x1, x2;
  cin >> x2;
  int a = 0, b = 0;
  b = primeArray[x2];
  x0 = 99999999;
  for (int i = x2 - b + 1; i <= x2; i++) {
    a = primeArray[i];
    x0 = min(i - a + 1, x0);
  }
  cout << x0;
  return 0;
}
