L1-006 連續因子 天梯

• 2020 年 8 月 14 日
• 筆記
• 天梯賽

思路：

素數只有1和本身
合數 暴力枚舉 把連續因子最大的記錄下來

注意：

AC程式碼

//思路：
//素數只有1和本身
//合數 暴力枚舉 把連續因子最大的記錄下來 
#include<iostream>
#include<cmath>
using namespace std;
int main() {
	int N; //輸入所求數字
	cin >> N;
	int count = 0; //計數器
	int start = 0; //連續最多因子的開始
	int max_count = 0; //最大因子個數
	int temp, j; // temp, j臨時變數
	for (int i = 2; i <= sqrt(N); i++) {
		for (temp = N, j = i; temp % j == 0; j++) {
			count++;
			temp /= j;
		}
		if (count > max_count)
			start = i, max_count = count; // 記錄 最多連續因子&連續因子個數
		count = 0; // 計數器歸零 
	}
	//output 
	if (max_count) {
		cout << max_count << endl;
		cout << start;
		for (int i = 0; i + 1 < max_count; i++) {
			cout << "*" << ++start;
		}
	}
	else // 素數情況
		cout << 1 << endl << N;
	return 0;
}