1.题目要求求连续的质因数。
2.最开始卡在最后一个测试点中，后来经过对偶数情况的优化，发现仍然超时，于是考虑是奇数情况下超时，实际上，最后一个测试例子应该是一个非常大的质数；
3.把情况分为奇数和偶数，
1）奇数情况下，答案肯定为1个，遇到第一个整除的数，则直接输出；
但是采用遍历至n时，最后一个测试例子会超时，于是采用质因数分解的算法：
质因数分解算法如下：
情况一：当n是素数时，n的质因素要么是n本身；
情况二：在除去最大质因素的情况下，一定小于等于sqrt（n），如2*17=34，sqrt（34）=5，除去最大质因素17，剩下的质因素小于5 ；
于是，把时间复杂度降为o（sqrt（n）），最终一个例子通过
2）偶数情况下，当n小于6时，只有1个，但是当n大于6时，肯定有两个以上的连续因数，必然包含2*3；
于是我采用了计算各种情况下连续因数相乘时，因数的最大值是多少（即小于INT_MAX），答案如下：
[c language=”++”]
<strong>//下面是质因素数组，虽然最后没有对AC提供帮助，但是可以优化时间复杂度
//偶数情况下，除了2，其他情况下至少有两个连续的因数，2*3
//当已经有2个因数后，接下来只需要求3个因数的情况，在连续3个因数的情况下，满足要求的最大值是1287*1288*1289，所以取边界值1290
//当已经有3个连续因素后，接下来只需要求4个因数的情况，在连续4个因素的情况下，满足要求的最大值是211*212*213*214，所以取边界值215
//其他同理
vector<int> maxFactor = { INT_MAX, n, (int)((double)sqrt(n) + 1), 1290, 215, 73, 35, 21, 14, 10, 0 };//3~13</strong>
[/c]
3）由这道题目想到的其他问题：
连续两个数相乘，肯定可以被2整除，因为连续的两个数，必然包含偶数
连续三个数相乘，肯定可以被6整除（lcm（2，3）），因为连续的三个数，必然覆盖3的倍数和2的倍数
连续四个数相乘，肯定可以被12整除（lcm（2，3，4）），连续的三个数，必然覆盖2，3，4的倍数
连续若干个数都符合上述特征。
Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3*5*6*7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.
Input Specification:
Each input file contains one test case, which gives the integer N (1<N<231).
Output Specification:
For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format “factor[1]*factor[2]*…*factor[k]”, where the factors are listed in increasing order, and 1 is NOT included.
Sample Input:
630
Sample Output:
3 5*6*7
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
//2147483646
void dfsFactor(long long n, long long preNum, vector<int>&factor, vector<vector<int>>&ans,int&factorSize)
{
if (n % (preNum + 1) == 0)
{//因数连续，继续DFS
factor.push_back(preNum + 1);
dfsFactor(n / (preNum + 1), preNum + 1, factor, ans, factorSize);
}
else if (!factor.empty() && factor.size() > factorSize)
{//不连续时，如果连续因数的数量大于上次最大值，则压入答案中
factorSize = factor.size();
ans.push_back(factor);
}
}
bool cmp(const vector<int>&a, const vector<int>&b)
{
if (a.size() > b.size())
return true;
else if (a.size() == b.size() && a[0] < b[0])
return true;
else return false;
}
int main(void)
{
//分为奇数和偶数情况，奇数情况，肯定不能被6整除，最多只有一个因素，因此分情况处理
int n;
cin >> n;
if (n % 2 == 1)
{//奇数情况下，采用质因素分解的算法
/*
情况一：当n是素数时，n的质因素要么是n本身
情况二：在除去最大质因素的情况下，一定小于等于sqrt（n），如2*17=34，sqrt（34）=5，除去最大质因素17，剩下的质因素小于5
*/
int temp = (int)((double)sqrt(n) + 1);
for (int i = 2; i <= temp; ++i)
{
if (n%i == 0)
{
cout << "1" << endl;
cout << i << endl;
return 0;//直接返回
}
}
cout << "1" << endl;
cout << n << endl;
}
else
{
//下面是质因素数组，虽然最后没有对AC提供帮助，但是可以优化时间复杂度
//偶数情况下，除了2，其他情况下至少有两个连续的因数，2*3
//当已经有2个因数后，接下来只需要求3个因数的情况，在连续3个因数的情况下，满足要求的最大值是1287*1288*1289，所以取边界值1290
//当已经有3个连续因素后，接下来只需要求4个因数的情况，在连续4个因素的情况下，满足要求的最大值是211*212*213*214，所以取边界值215
//其他同理
vector<int> maxFactor = { INT_MAX, n, (int)((double)sqrt(n) + 1), 1290, 215, 73, 35, 21, 14, 10, 0 };//3~13
vector<int> factor(0);
vector<vector<int>>ans(0);
int factorSize = 0;
for (long long i = 1; i <= min(n, maxFactor[factorSize + 1]); i++)
{
if (n % (i + 1) == 0)
{
dfsFactor(n, i, factor, ans, factorSize);
factor.clear();
}
}
sort(ans.begin(), ans.end(), cmp);
cout << ans[0].size() << endl;
for (int i = 0; i < ans[0].size(); i++)
{
cout << ans[0][i];
if (i != ans[0].size() – 1)
cout << "*";
}
cout << endl;
}
return 0;
}
[/c]