[CodeForces948B]Primal Sport（数论）

Description

题目链接

Solution

设f(x)为x的最大质因子

那么由题意易得(X_1)的范围在([X_2-f(X_2)+1,X2])

同理(X_0)的范围在([X_1-f(X_1)+1,X1])

枚举(X_1)即可

Code

#include<cstdio>
#include<algorithm>
using namespace std;

int n,tmp,Ans=1e9,f[1000010];

void Init(){
	for(int i=2;i<=n;++i){
		if(!f[i]) for(int j=2;i*j<=1000000;++j)
			f[i*j]=i;
		f[i]=i-f[i]+1;
	}		
}

int main(){
	scanf("%d",&n);
	Init();
	for(int i=f[n];i<=n;++i) Ans=min(Ans,f[i]);
	printf("%d
",Ans);
	return 0;
}