欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习96——1096 Consecutive Factors

程序员文章站 2022-06-07 11:46:10
...

题目

PTA甲级考试真题练习96——1096 Consecutive Factors

思路

对于每个质因子(小于等于num)i,从i开始遍历直到乘积不能被整除,记录其中最大序列

坑点

注意不要忽略为质数的情况,应该就输出质数本身,否则最后两个测试点运行超时

代码

#include <iostream>
using namespace std;
int main()
{
	int num;
	int maxlen = 0;
	int start, end;
	cin >> num;
	int sqrtn = sqrt((double)num);
	for (int i = 2; i <= sqrtn; ++i) {
		if (num % i != 0)
			continue;
		int j = i;
		int k = j;
		while (true) {
			k *= j + 1;
			if (num % k != 0) break;
			j++;
		}
		if (j -i + 1 > maxlen) {
			maxlen = j - i + 1;
			start = i;
			end = j;
		}
	}
    if(maxlen == 0){
        cout<<1<<endl;
        cout<<num;
        return 0;
    }
	cout << maxlen << endl;
	cout << start;
	for (int i = start+1; i <= end; ++i) {
		cout << "*" << i;
	}
	return 0;
}