关于算法-数据结构: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;
}