利用线性筛找到最大质因数，然后找符合条件的ans
#include <bits/stdc++.h>
using namespace std;
#define N 100011
#define M 1000011
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<ll,int> PII;
int n,m,q,ans;
int arr[M];
int prime[M];
int f[M];
void xxs(int x)///线性筛
{
int pos=0;
for(int i=2;i<=x;i++)
{
if(!arr[i]) prime[++pos]=f[i]=i;
for(int j=1;j<=pos;j++)
{
if(i*prime[j]>n) break;///范围
arr[i*prime[j]]=1;
f[i*prime[j]]=max(f[i],prime[j]);///重点-记录最大质因数
if(i%prime[j]==0) break; ///最小质因数
}
}
}
int get(int x)
{
if(!arr[x]) return inf;///素数百搭就inf
return x-f[x]+1;///复合条件的公式
}
int main()
{
cin>>n;
xxs(M);
ans=inf;
for(int i=get(n);i<=n;i++)///在这个范围遍历
{
ans=min(ans,get(i));
}
if(ans>=inf) cout<<-1;
else cout<<ans;
return 0;
}
