关于算法-数据结构:PAT甲级1096-Consecutive-Factors

题目粗心：

给出一个正整数 N, 求一段间断的整数，使得 N 能被这段间断整数的乘积整除。如果有多个计划，输入间断整数个数最多的计划; 如果还有多种计划，输入其中第一个数最小的计划。

算法思路：

刚开始审题不当认为是质因子合成，导致节约了很多工夫，该题的想法也比拟直观，咱们遍历从 2 到 N 之间的每一个数字，用 consecutiveMulti 保留每一个能够被 N 整除的间断序列的乘积，并且应用 len 保留最长的序列长度，begin保留最长的序列的起始数字，让 consecutiveMulti 一直累乘直到不能被 N 整除地位（就相似于从 2 开始始终乘以 3,4,5,6… 直到 N 不能整除该间断乘积为止，而后再接着从 3 开始始终乘以 4，5，6，7，8… 以此类推），而后更新长度 len 和起始地位 begin，这里得留神 i 的含意是每一个间断序列的起始地位，咱们这里应用nextNum 保留以后序列的下一个待乘的数字，初始为 i，而后在循环中，consecutiveMulti会乘以 nextNum, 并且其长度能够应用nextNum-i+1 来代替，因为在数字 i 和nextNum之间的数字都是间断的，每次更新 nextNum 加一即可。其实在这里不必遍历 2 到 N，只用遍历到根号 N 即可，因为，第一，不存在 2 个因子都大于更号 N。第二，N 如果存在大于根号 N 的因子肯定无奈和后面的因子组成间断序列。第三，如果在 2 到根号 N 中没有 N 的因子, 那么在根号 N 和 N 之间也必然不会有 N 的因子，N 的因子只有 1 和 N 自身，然而题目因为对于 1 不思考，所以在 2 和根号 N 之间没有解的时候只有长度为 1 的间断序列 N。

提交后果：

AC 代码：

#include <cstdio>
#include <cmath>

using namespace std;

int main(){
    int N;
    scanf("%d",&N);
    int sqrt_N = (int)sqrt(N * 1.0);
    int begin = 0;
    int len = 0;
    for (int i = 2; i <=sqrt_N ; ++i) {
        int consecutiveMulti = 1;// 从数字 i 开始的局部间断乘积
        int nextNum = i;// 以后序列前面待乘的一个数字
        while (true){
            consecutiveMulti *= nextNum;
            if(N%consecutiveMulti!=0) break;// 无奈整除以后序列退出循环
            // 能够整除，更新长度
            if(len<nextNum-i+1){
                len = nextNum-i+1;
                begin = i;
            }
            ++nextNum;// 更新下一个待乘的数字
        }
    }
    if(len==0){// 阐明不存在 2 到根号 N 的数字局部乘积能够整除 N，也即是以后的 N 只有一个因子(它本人)。printf("1\n%d",N);
    }else {printf("%d\n",len);
        for (int i = begin; i < begin+len; ++i) {printf("%d",i);
            if(i<begin+len-1) printf("*");
        }
    }
    return 0;
}