PTA例题连续因子连续因子PTA题目描述一个正整数 N 的因子中可能存在若干连续的数字. 例如 630 可以分解为 3×5×6×7, 其中 5、6、7 就是 3 个连续的数字. 给定任一正整数 N, 要求编写程序求出最长连续因子的个数, 并输出最小的连续因子序列.输入格式输入在一行中, 给出一个正整数 N1 N 231.输出格式首先在第 1 行输出最长连续因子的个数然后在第 2 行中按 因子1*因子2*……*因子k 的格式输出最小的连续因子序列, 其中因子按递增顺序输出, 1 不算在内.输入样例630输出样例35*6*7题目解析首先我们需要明确①如果一个正整数N拥有连续因子序列, 那么这个序列的乘积一定是不超过正整数N本身的.②长度已经确定的连续因子序列, 只需确定其中第1个数便可确定整个序列当然确定第2个数、第3个数等都可以确定整个序列. 因此可以通过长度和第1个数来确定连续因子序列.③长度已经确定的连续因子序列中, 第1个数为2的序列是最小的序列乘积最小, 并且第1个数越大, 序列越大序列乘积越大. 此处的最小和最大即题目所表述的, 是针对确定长度下的连续因子序列来讲的.题目中, 正整数N的最大值为231- 1. 分别作如下计算①231- 1 210* 210* 210* 2 - 1 1024 * 1024 * 1024 * 2 - 1 2147483648 - 1 2147483647十位数即可以输入的最大整数为2147483647.②2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 479001600九位数长度为11的最小连续因子序列, 乘积为479001600, 记作A.③2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 6227020800十位数长度为12的最小连续因子序列, 乘积为6227020800, 记作B.由于B 231- 1长度为12, 第1个数为2的连续因子序列乘积已经比这个数大了, 那该序列就不可能是这个数的连续因子序列, 而长度为12, 第1个数为其他数的连续因子序列的乘积更大, 就更不可能是这个数的连续因子序列了. 那么对于比231- 1更小的数而言, 长度为12的连续因子序列一定比它们更大, 也不可能成为它们的连续因子序列.由于231-1 A长度为11, 第1个数为2的连续因子序列乘积尚且比这个数小, 那该序列有可能成为这个数的连续因子序列.因此我们设计代码时, 就先在长度为11的连续因子序列找有没有正整数N的连续因子序列, 如果找着找着乘积超过了正整数N, 那就在长度-1后的连续因子序列中继续找, 如果找着找着乘积超过了正整数N, 那就在长度再-1的连续因子序列中继续找, 以此类推, 直到在长度为1的连续因子序列中继续找, 已经到了这种地步其实就是在找除了1以外, 自身最小的约数了, 质数找到的是自己本身.已经知道质数最终会找到自己本身了, 那么可以先设计一个函数来判断N是否为质数, 如果是质数则直接输出结果. 要是不这样做的话, 当质数特别特别大并且接近最大值, 那么就算是经历千辛万苦后i的值总算为1了,j的值也得增长到N, 第二层循环将进行N - 1次, 再加上之前经历的循环, 程序应该是崩得不能再崩了.因此, 我们可以设计嵌套循环, 共三层.第一层for (int i 11; i 1; i--)决定连续因子序列的长度第二层for (int j 2; ; j)决定连续因子序列的第1个数第三层for (int k 1; k i; k)用于计算连续因子序列的乘积.附上我的代码实现#includestdio.hintzhishu(intn)//判断为质数则返回1, 判断为合数则返回0.{intflag1;if(n2){returnflag;}if(n0||n1)//其实本题压根不输入0和1, 不用判断0和1, 但是出于习惯还是写到这里了{return!flag;}for(inti2;i(n/i);i){if(n%i0){return!flag;}}returnflag;}intmain(){intN0;scanf(%d,N);if(zhishu(N)){printf(%d\n,1);printf(%d,N);printf(\n);return0;}for(inti11;i1;i--)//确定连续因子序列的长度{for(intj2;;j)//确定连续因子序列的第一个数{longlongmul1;//配合第三层循环, 用于计算连续因子序列的乘积. 由于乘积可能会很大, 所以用long long类型防溢出for(intk1;ki;k)//i是连续因子序列的长度, 完成i次循环后, 可以得到连续因子序列的乘积{mul*(jk-1);}if(mulN)//必须先判断连续因子序列的乘积是不是大于N, 大于N则削减连续因子序列长度后再从第1个数为2的情况开始找.{//否则如果出现乘积大于N但是乘积可以被N整除的情况时, 会被错误地当成所求情况break;}if(N%mul0){printf(%d\n,i);//打印输出找到的连续因子序列的长度for(intk1;ki;k){if(k!1){printf(*);//连续因子序列数中, 除了第1个数, 其余数打印时都有一个前置的*}printf(%d,jk-1);//第3层循环, 逐次打印j, j 1, j 2……共i个数}printf(\n);//原题最后有空行, 因此这里配合一下return0;//已经找到了所输出的正整数N的连续因子序列, 结束函数}}}return0;}