《算法笔记上机实验指南》第4章 入门篇（2）---算法初步5.5质因子分解

pat A1096

题意：

输入：

1.输入n

输出：

1.先输出最大连续因子的个数 2.依次连续输出最小的连续因子

解题思路：

参考代码：

#include<iostream> #include<cmath> typedef long long LL; using namespace std; /* 解题思路： 1.一个数不会除了自身外不会被超过根号n的数整除，所以从2--根号n循环 2.从2--根号n开始循环for+while的循环：1.for：遍历每一个数，while：寻找所有连续的因子 3.按要求输出 */ int main() { LL n; cin >> n; LL sqr=(LL)sqrt(1.0*n),ansI=0,ansLen=0; //ansI表示连续的第一个数 for(LL i=2; i<=sqr; i++) //寻找每一个可能的因子，注意对于能开平方的数字，也要能输出其因子，也就是i<=sqr { LL temp=1,j=i; while(1) //寻找连续的因子，两个下标i，j；i表示从i这个数开始，j表示最后一个位置的数，由于是连续的所以连续的因子的长度为j-i+1,如果其长度发生变化，则也更新ansI和其长度ansLen，j不断的自增 { temp*=j; if(n%temp!=0) break; if(j-i+1>ansLen) //j-i+1也表示个数 { ansI=i; //ansI表示从i出开始 ansLen=j-i+1; //更新它的长度 } j++; //j++不断的去寻找下一个 } } if(ansLen==0) //如果长度为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) //表示n个长度，则输出n-1个乘号 cout << "*"; } } return 0; }

注意事项：

注意对于能开平方的数字，也要能输出其因子，也就是i<=sqr

for(LL i=2; i<=sqr; i++) //寻找每一个可能的因子，

对于素数，就输出自身，连续因子长度为0；对于能开平方的数，输出其开平方，长度为1；对于质因子的幂次方，则输出该质因子，长度为1…