一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N要求编写程序求出最长连续因子的个数并输出最小的连续因子序列。输入格式：输入在一行中给出一个正整数 N1N2 31 。输出格式：首先在第 1 行输出最长连续因子的个数；然后在第 2 行中按 因子1因子2……因子k 的格式输出最小的连续因子序列其中因子按递

#include #include #include using namespace std; int main() { long long n,ans=0;//注意long long cin>>n; vector f;//存储因子 for(int i=2;i<=sqrt(n);i++)//这里要用到sqrt，降低时间复杂度 { if(n%i==0) { f.push_back(i); n/=i; i--;//这里i--，是因为如果n能分解成两个相同的质因数，那么i不应该改变，还需再次判断 } } f.push_back(n);//将最后一个因子存入数组 int len=f.size(); for(int i=0;i<len;i++)//枚举起始位置 { int j=i+1; while(j<len)//枚举结束位置 { int tmp=1; for(int k=i;k<=j;k++) tmp*=f[k];//计算连续的因子乘积 if(n%tmp==0) j++;//如果能被整除，说明是连续的因子，结束位置j加1 else break;//否则跳出循环 } if(j-i>ans)//如果当前连续因子个数大于原来的连续因子个数 { ans=j-i; cout<<ans<<endl; cout<<f[i]; for(int k=i+1;k<j;k++) cout<<"*"<<f[k];//输出最小的连续因子序列 } } return 0;