#include <bits/stdc++.h>
int isprime[1000001];
int n, i, j;
int main() {
  scanf("%d", &n);
  for (i = 2; i <= n; i++) {
    if (isprime[i] != 0) continue;
    for (j = i * 2; j <= n; j += i) isprime[j] = i;
  }
  j = n - isprime[n] + 1;
  for (i = n - 1; i >= n - isprime[n] + 1; i--)
    if (i - isprime[i] + 1 < j) j = i - isprime[i] + 1;
  printf("%d", j);
  return 0;
}
