PAT甲级1096.

目录

A1096

题目

样例

输入:

630

输出:

3
5*6*7

思路和坑点

　　直接对所有可能的连续因子进行统计，然后比较筛选出最合适的答案。考虑到对于一个非素数来说，其因子不会超过sqrt（）。
　　坑点:
　　注意特判素数的情况，个数为1，因子为自己本身。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    vector<int> out,temp;               //使用数组保存因子，temp为临时结果，out为最终结果 
    int n;
    cin>>n;
    int sqr=(int)sqrt(1.0*n);           //如果有连续因子，则因子小于等于n开根号 
    for(int i=2;i<=sqr;i++){
        int t=n;
        for(int j=i;;j++){              //从i开始获取连续的因子 
            if(t%j==0){
                temp.push_back(j);
                t/=j;
            }
            else break;                 //如果遇到不连续的则挑出循环 
        }
        if(temp.size()>out.size())      //比较更新结果 
            out=temp;
        temp.clear();                   //temp清空，准备接受下一组结果 
    } 
    if(out.size()==0)                   //特判素数只有1和其自身 
        printf("1\n%d",n);
    else{
        int size=out.size();            //输出多因子的结果 
        printf("%d\n",size);
        for(int i=0;i<size;i++){
            if(i) putchar('*');
            printf("%d",out[i]);
        }
    }
    return 0;
}