L1-6. 連續因子

L1-6. 連續因子

一個正整數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

題解：暴力。。。。暫時沒想到更好的方法。。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

int main()
{
    int N,cnt=0,zhtai=1;
    int n=0; 
    char a[1010];
    char temp[1010];
    int sq; 
    scanf("%d",&N);

    sq=(int)sqrt(N)+1; 

    //從該數的根号往前掃 
    for(int i=sq;i>=2&&zhtai;--i){
        cnt=0;
        if(N%i==0){
            temp[cnt++]=i;
            int t=N/i;
            for(int j=i-1;j>=2;--j)
            {
                if(t%j==0){
                    temp[cnt++]=j;
                    t=t/j;
                    if(j==2) {
                        zhtai=0;
                    }
                }
                else{
                    temp[cnt]=0; break;
                }
            }
            //不斷更新連續因子的個數和儲存連續因子
            if(cnt>=n){
            strcpy(a,temp);
            n=cnt; 
        }
    }
 }
    if(n==0)printf("%d\n%d",1,N);
    else{
        printf("%d\n",n);
        for(int j=n-1;j>=0;--j){
            printf("%d",a[j]);
            if(j!=0){
                printf("*");
            }
            else{
                printf("\n");
            }
        }
    } 

 return 0;
}