GPLT-L1006 连续因子 (20 分)

一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。

输入格式：

输入在一行中给出一个正整数 N（1<N<2^​31）。

输出格式：

首先在第 1 行输出最长连续因子的个数；然后在第 2 行中按因子1*因子2*……*因子k的格式输出最小的连续因子序列，其中因子按递增顺序输出，1 不算在内。

输入样例：

630

输出样例：

3
567

作者:陈越
单位:浙江大学
代码长度限制:16 KB
时间限制:400 ms
内存限制:64 MB

思路：

暴力，自己写的时候有两分一直拿不到，所以借鉴了一下其他大佬的代码，但是太久远找不到出处了。详细解法在代码中注释了。

代码：

#include<stdio.h>
#include<math.h>
int main()
{
	int n;
	int i,j,k,len;
	scanf("%d",&n);
	k=sqrt(n);
	for(len=12;len>=1;len--)//2^31在12！~13！之间，因此连续因子最大长度为12
	{
		for(int start=2;start<=k;start++)//找从strat开始的连续因子
		{
			int ans=1;
			for(i=start;i-start<len;i++)//找到i为止
				ans*=i;
			if(n%ans==0)//如果ans是n的因子，输出结果
			{
					printf("%d\n%d",len,start);
					for(j=start+1;j-start<len;j++)
						printf("*%d",j);
					return 0;
			}

		}
	}
	printf("1\n%d",n);
	return 0;
}