L1-006. 连续因子-PAT团体程序设计天梯赛

一个正整数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

[Update v2.0] 由github用户littlesevenmo提供的更高效的解法：
不用算连续因子最多不会超过12个，也不需要三重循环，两重循环即可，直接去计算当前部分乘积能不能整除N
分析：1、如果只有一个因子，那么这个数只能为1或者质数。因此我们主要去计算两个及以上因数的情况。
2、在有两个及以上的数连乘中，因数的最大上限为sqrt(N) + 1
3、因此思路就是，不断构造连乘，看连乘的积是否是N的因数，如果是，则看这部分连乘的数的个数是否比已记录的多。
4、用变量first记录连乘的第一个数字，这里我把它赋初值为0，如果在寻找N的因数过程中，first没有改变，那么就表明N是1或者是一个质数～

#include <iostream>
#include <cmath>
using namespace std;
long int num, temp;
int main(){
    cin >> num;
    int first = 0, len = 0, maxn = sqrt(num) + 1;
    for (int i = 2; i <= maxn; i++) {
        int j; 
        temp = 1;
        for (j = i; j <= maxn; j++) {
            temp *= j;
            if (num % temp != 0) break;
        }
        if (j - i > len) {
            len = j - i;
            first = i;
        }
    }
    if (first == 0) {
        cout << 1 << endl << num;
    } else {
        cout << len << endl;
        for (int i = 0; i < len; i++) {
            cout << first + i;
            if (i != len - 1) cout << '*';
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

long int num, temp;

int main(){

cin >> num;

int first = 0, len = 0, maxn = sqrt(num) + 1;

for (int i = 2; i <= maxn; i++) {

int j;

temp = 1;

for (j = i; j <= maxn; j++) {

temp *= j;

if (num % temp != 0) break;

}

if (j - i > len) {

len = j - i;

first = i;

}

if (first == 0) {

cout << 1 << endl << num;

} else {

cout << len << endl;

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

cout << first + i;

if (i != len - 1) cout << '*';

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版