[数据结构与算法]PTA 天梯赛 L1-006 连续因子 C++实现

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

输入格式：

输入在一行中给出一个正整数 N（1<N<231）。

输出格式：

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

输入样例：

630

输出样例：

3
5*6*7

解题思路：

找到最初的因子数和有多少个因子即可

#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int main() 
{
	int n;
	cin >> n;

	int cnt = 0, max_cnt = 0; //cnt为数有多少因子 max_cnt为最大因子数目
	int start; //最初的因子数

	for (int i = 2; i <= sqrt(n); i++) 
	{
		int temp = n;
		int p = i;
		cnt = 0;

		while (temp % p == 0)
		{
			temp = temp / p;
			p++;
			cnt++;
		}

		if (cnt > max_cnt) 
		{
			max_cnt = cnt;
			start = i;
		}
	}

	if (max_cnt != 0) 
	{
		cout << max_cnt << endl;
        
        //输出控制
        int flag = 1;
		for (int i = 0; i < max_cnt; i++) 
		{
            if(flag > 1)
            {
                cout << "*";
            }
			cout << start + i;
			flag++;
		}
	}
	else 
	{
		cout << 1 << endl << n;
	}
}

运行结果：