一道时间超限的题,求帮忙优化
问题描述给定一个数x,求正整数y≥2,使得满足以下条件:
1.y-x的绝对值最小
2.y的质因数分解式中每个质因数均恰好出现2次。
输入描述
第一行输入一个整数T(1≤T≤50)
每组数据有一行,一个整数x(1≤x≤10^18)
输出描述
对于每组数据,输出一行y-x的最小绝对值
输入样例
5
1112
4290
8716
9957
9095
输出样例
23
65
67
244
70
代码:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int f(int n){
int i,k;
if(n==1) return 1;
for(i=2;i<=n;i++){
k=0;
while(n!=i){
if(n%i==0){
n=n/i;
k++;
if(k>1) return 0;
}
else break;
}
}
return 1;
}
int main(void){
int T,n,n1,n2;
long long int x,y1,y2;
scanf("%d",&T);
while(T--){
scanf("%lld",&x);
n1=sqrt(x);
n2=n1+1;
while(!f(n1)) n1--;
while(!f(n2)) n2++;
y1=n1*n1;
y2=n2*n2;
if(n1!=1)
printf("%lld\n",((x-y1)>(y2-x))?(y2-x):(x-y1));
else printf("%lld\n",y2-x);
}
}
我的思路是先把x开根号,左边整数为y1,右边为y2,判断y1,y2是不是可以分解成每个质因数只出现一次的数,不是的话分别向左右扩散,直到找到。
这个方法显示时间超限了,想问问各位大佬有没有优化的方法?
[此贴子已经被作者于2018-5-18 15:18编辑过]