#include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6+, inf = 0x3f3f3f3f;

 bool no_prim[maxn];

 int prim[maxn];

 int cnt=;

 int f[maxn];

 void init(){

     no_prim[]=no_prim[]=true;

     for(int i=;i<maxn;i++){

         if(!no_prim[i]){

             prim[cnt++]=i;

             for(int j=i*;j<maxn;j+=i){

                 f[j]=max(f[j],i);

                 no_prim[j]=true;

             }

         }

     }

 }

 int main(){

     init();

     int X;

     scanf("%d",&X);

     int ans=inf;

     for(int i=X-f[X]+;i<=X;i++){

         if(!no_prim[i]) continue;

         ans=min(ans,i-f[i]+);

     }

     printf("%d\n",ans);

     return ;

 }