【链接】 我是链接,点我呀:)
【题意】
题意
【题解】
考虑怎么得到数字x2=N,假设是质数p的倍数
那么x1肯定在x2-p+1~x2这个范围内才行
因为p的倍数要刚好大于等于x1,
所以x1肯定是在这两个倍数之间才行
结果已经很显然了
肯定让p的值越大越好。
这样得到的x1才可能越小。
枚举x1在x2-p+1~x2之间。
用同样的方式得到x0就好。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n;
int x0,x1,x2;
int maxfac(int x){
int j = x;
for (int i = 2;i*i<=x;i++){
if (x%i==0){
while (x%i==0){
x/=i;
}
j = i;
}
}
if (x>1) j = x;
return j;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> x2;
int p = x2-maxfac(x2)+1;
int ans = x2;
for (int x1 = p;x1 <= x2;x1++){
int temp = maxfac(x1);
if (temp!=x1){
x0 = x1-temp+1;
ans = min(ans,x0);
}
}
cout<<ans<<endl;
return 0;
}