L1-006 连续因子（20）（思路+测试点分析）

L1-006 连续因子（20 分）

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

输入格式：

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

输出格式：

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

输入样例：

输出样例：

3

5*6*7

思路：

题目要求输入一个数，输出最长的最小连续因子，而输出数据特征：起始值，连续长度。由于数N在【sqrt(N)，N】不可能存在连续因子，所以我们只需在【2，sqrt(N)】区间以不同的起始值，更新最终起始值(start)和连续因子长度(maxcount)即可

注意：对于素数，连续因子就是本身，且长度为1（测试点5/6）

#include<iostream>

#include<cmath>

using namespace std;

int main() {

	int N, temp;

	int count = 0, maxcount = 0, start = 0;

	cin >> N;

	for (int i = 2; i <= sqrt(N) ; i++) {

		temp = N;

		count = 0;

		int j = i;

		while (temp%j==0) {

				temp /= j++;

				count++;

		}

		if (count > maxcount) {

			maxcount = count;

			start = i;

		}

	}

	if (maxcount) {

		cout << maxcount << endl;

		for (int i = 0; i < maxcount; i++) {

			cout << start + i;

			if (i != maxcount - 1)

				cout << "*";

		}

	}

	else

		cout <<"1"<<endl<< N;

	return 0;

}

巴特西

L1-006 连续因子（20）（思路+测试点分析）

输入格式：

输出格式：

输入样例：

输出样例：

思路：

最新文章

热门文章

巴特西

L1-006 连续因子（20）（思路+测试点分析）

输入格式：

输出格式：

输入样例：

输出样例：

思路 ：

最新文章

热门文章

思路：