1059 Prime Factors 数论
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format $$N=p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m} $$
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification:
Factor N in the format N=p1^k1p2^k2...pm^km
Sample Input:
97532468
Sample Output:
97532468=2^211171011291
思路：
先求素数表，然后对于每一个素数尝试去分解题目所提供的值，分解至无法整除为止记录下来，这里记录用了一个结构体 factor 表示一次分解的结果 x表示底，cnt表示次方。这里要注意特判1的情况否则1不会输出。
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 100010;
int prime[maxn], pNum = 0;
bool p[maxn] = {0}; // p[i] == false 为质数
void findPrime(){
for(long int i = 2; i < maxn; i++){
if(p[i]){
continue;
}
prime[pNum++] = i;
for(long int j = i + i; j <= maxn; j += i){
p[j] = true;
}
}
}
struct factor {
long int x;
int cnt;
} fac[10];
int main() {
long int value;
cin >> value;
if(value == 1){
printf("1=1");
return 0;
}
long int bValue = value;
findPrime();
int fNum = 0;
for(int i = 0; i < pNum; i++){
long int j = prime[i];
if(bValue % j != 0){
continue;
}
factor f = factor{};
f.x = j;
int cnt = 0;
while(bValue % j == 0){
bValue /= j;
cnt++;
}
f.cnt = cnt;
fac[fNum++] = f;
if(bValue == 0){
break;
}
}
printf("%ld=", value);
for(long int i = 0; i < fNum; i++){
printf("%ld", fac[i].x);
if(fac[i].cnt > 1){
printf("^%d", fac[i].cnt);
}
if(i != fNum - 1){
printf("*");
}
}
return 0;
}