PTA天梯赛的题目,不知道为什么部分测试点错误以及一个测试点超时运行,如何修进?
--以下是题目:一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。
输入格式:
输入在一行中给出一个正整数 N(1<N<2
31
)。
输出格式:
首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按 因子1*因子2*……*因子k 的格式输出最小的连续因子序列,其中因子按递增顺序输出,1 不算在内。
输入样例:
630
输出样例:
3
5*6*7
时间限制:400ms,超时了就算不过
--以下是我的代码:
程序代码:
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<math.h> int main() { //如果我没理解错题目的意思的话可能是下面的例子意思 //比如输入630,找因子可能是2*3*5*21,也可能是3*5*6*7,此时5*6*7是最长的连续因子 //然而我下边的代码在PTA结果测试中部分报错,还有一个测试点是超时,请各位大佬帮忙看看为什么部分错误以及如何修进代码 int vl, vll, i = 2, j = 2, maxl = 0, len = 0, end = 1; scanf("%d", &vl); //输入 while (i < sqrt((int)vl)) //第一层循环,实现,以i为分解因子的开头(第一次从2开始) { j = i; while (j < sqrt((int)vl)) //第二层循环,实现,因子分解并求最长值 { vll = vl; //vll用于取出vl值来进行除以,保证原输入值不变(因为要多次寻找) if (vll % j == 0) { len += 1; //算len长 vll = vll / j; } else { len = 0; } if (len > maxl) //求最大len长:maxl { maxl = len; end = j; //end用于记录最长值末尾的数字,便于后面输出最长部分 } j++; if (vll == 1) //这里是为了减少运算量(但还是有一个测试点超时运算) { break; } } i++; } printf("%d\n", maxl); for (;maxl > 0;maxl--) //输出 { if (maxl != 1) { printf("%d*", end - maxl + 1); } else { printf("%d", end); } } return 0; }
目前就是说题目给的输入和输出效果实现没问题,但PTA不告诉你其他的测试点用的什么输入数据,我自己也查找不出来,请求各位大佬帮忙查看一下。