题目描述

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

输入格式

输入在一行中给出一个正整数 N（1<N<2​^31）。

输出格式

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

输入样例

630

输出样例

3
5*6*7

题解思路

1.最长连续因子只能从1到sqrt(n)里找。
2.最长连续因子不会超过31项（粗略计算）。

故我们直接让从[2, sqrt(n)]中求最长的连续因子即可。连续因子的个数为0（说明n是一个质数），则连续因子的个数为1，因子为n本身。粗略计算代码的时间复杂度为： 图片.png

题解代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n = 0;
    LL res = 0;
    LL start = 0;
    scanf("%lld", &n);
    LL up_bound = (LL)sqrt(n) + 2;
    for(LL i = 2; i <= up_bound; i++){
        LL t = n;
        for(LL j = i; j <= n; j++){
            if(t % j == 0){
                t /= j;
            } else {
                if(res < j - i){
                    res = j - i;
                    start = i;  
                }   
                break;  
            }
        } 
    }
    if(res == 0){
        res = 1;
        start = n;
    }
    printf("%lld\n", res);
    printf("%lld", start);
    for(LL i = start + 1; i < start + res; i++){
        printf("*%lld", i);
    }
    return 0;
}