Given any positive inerger N, you are supposed to find all of its prime factors,and write them in the format: N =p1k1*p2k2* '''*pm^km.
#include <iostream>
using namespace std;
const int N = 10000;
int prime[N], pNum = 0;
bool p[N] = { 0 };
//定义存放质因数和其出现次数的结构体
struct factor {
int x = 0, cnt = 0;
}fac[10];
//找出10000以内所有质数
void find_prime() {
for (int i = 2; i < N; i++) {
if (p[i] == false) {
prime[pNum++] = i;
for (int j = 2 * i; j < N; j += i) {
p[j] = true;
}
}
}
}
int main() {
long int n;
int num = 0;
int m;
cin >> n;
m = n;
find_prime();
//找出输入数的所有质因数
for (int i = 0; i < n; i++) {
if (n%prime[i] == 0) {
fac[num].x = prime[i];
fac[num].cnt = 0;
while (n%prime[i] == 0) {
fac[num].cnt++;
n /= prime[i];
}
num++;
}
}
//按规定格式输出
cout << m << "=";
for (int i = 0; fac[i].x != 0; i++) {
if (fac[i].cnt == 1&&(fac[i+1].x!=0)) {
cout << fac[i].x << "*";
}
//最后一个质因数后不加“*”
else if (fac[i + 1].x == 0) {
if (fac[i].cnt == 1) {
cout << fac[i].x << endl;
}
else
{
cout << fac[i].x << "^" << fac[i].cnt << endl;
}
}
else {
cout << fac[i].x << "^" << fac[i].cnt << "*";
}
}
return 0;
}
