PAT A1096 质因子分解

共计 596 个字符，预计需要花费 2 分钟才能阅读完成。

这道题没有用常规的从小到大分解质因子，而是要连续的质因子；
其实思路很简单，从 2~sqrt(n) 进行枚举，使得 n%temp 是否能够取余为 0，temp 为连续质因子的乘积。在每次迭代中记录最长的质因子序列和相应的起始值；
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
using std::vector;
typedef long long LL;
int main(){
LL n;
scanf(“%lld”,&n);
LL sqr=(LL)sqrt(1.0*n);
LL ansI=0,ansLen=0;
for(LL i=2;i<=sqr;i++){
LL temp=1,j=i;
while(1){
temp*=j;
if(n%temp!=0)
break;
if(j-i+1>ansLen){
ansI=i;
ansLen=j-i+1;
}
j++;
}
}
if(ansLen==0){
printf(“1\n%lld”,n);
}else{
printf(“%lld\n”,ansLen);
for(LL i=0;i<ansLen;i++){
printf(“%lld”,ansI+i);
if(i<ansLen-1){
printf(“*”);
}
}
}
system(“pause”);
return 0;
}