[PAT解题报告] Prime Factors
分解质因数——题目说n在long int范围内，一般32位机，long
int就是int。分解质因数采取最朴素算法，枚举x，注意x到sqrt(n)即可，如果n是合数的话，必然有一个质因数x不超过sqrt(n)。我们找到一个质因数，就用n不断地除这个数，算出它出现地次数，注意这样n也会自己变小的。最后，退出循环的时候，x
> sqrt(n)，这时如果n是1，说明已经分解完了，如果n > 1，说明原来的n还有这个质因数。
所以并不需要我们打质数表什么的，虽然x是不断+1枚举的，但是每次发现的如果x是n的因数，则一定是质因数。因为那些更小的质因数已经从n中约掉了。例如x
= 2时，我们从n中把2全都约去了，所以尽管会枚举4，6，8，10....，但是这些都会被直接跳过去。
简单举个例子，
（1） 比如n = 8, 我们发现质因数2的话，2 < sqrt(8), 用8 / 2除到1，发现次数是3，
n变为1，已经分解完了。
（2） 再比如n = 6,同样发现质因数2，次数1是1， n变为3，然后x也变为3，我们发现3 >
sqrt(3)，所以退出循环，然后发现n = 3 > 1，所以这个3也是一个质因数，出现次数只能是1。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int main() {
int n;
bool first = true;
scanf("%d",&n);
printf("%d=",n);
if (n == 1) {
puts("1");
return 0;
}
for (int i = 2; n / i >= i; ++i) {
int j = 0;
for (; n % i == 0; n /= i, ++j)
;
if (j) {
if (first) {
first = false;
}
else {
putchar('*');
}
printf("%d",i);
if (j > 1) {
printf("^%d", j);
}
}
}
if (n > 1) {
if (!first) {
putchar('*');
}
printf("%d",n);
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1059
投递韶音科技等公司10个岗位