PAT 甲级 1096 Consecutive Factors

给出一个数n，求把它分解为多个数的乘积后，这多个数最多有几个是连续的。这个数小于2^31，我的思路就是从2到sqrt(n)，分别计算从一个数开始的连续乘积，直到乘积结果超过n，sqrt(n)最大值为46340，而且最小的2乘到13都大于给定的最大的n，所以提前把所有的表打出来时间所需的很少，然后再用n去一个一个试，如果能被连续的乘积整除，就记录下这个连续的乘积有几位数，开始的数字是哪一位。如果没有找到满足的，就可认为它是素数，答案也就直接可以出来。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL; 
int t;
vector<LL> record[46350];

int main()
{
	cin>>t;
	int tmp=t;
	int maxn=sqrt(t+0.1);
	for(int i=2;i<=maxn;i++)
	{
		record[i].push_back(i);
		for(int j=i+1;;j++)
		{
			record[i].push_back(record[i][j-i-1]*j);
			if(record[i][j-i]>t)
			{
				record[i].pop_back();
				break;
			}
		}
	}
	int ans=-1,start=-1;
	for(int i=2;i<=maxn;i++)
	{
		for(int j=0;j<record[i].size();j++)
		if(t%record[i][j]==0)
		{
			if(ans<j+1)
			{
				ans=j+1;
				start=i;
			}
		}
	}
	if(ans==-1)
	{
		ans=1;
		start=t;
	}
	cout<<ans<<endl;
	cout<<start;
	for(LL i=start+1;i<start+ans;i++)
	{
		cout<<‘*‘<<i;
	}

	return 0;
}

PAT 甲级 1096 Consecutive Factors

原文：https://www.cnblogs.com/ambition-hhn/p/13055883.html