# 11020: 【原1020】分解质因数

### 题目描述

author: 梁晨锦 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1020

## Description

``````2=2

20=2*2*5
``````

## Output Format

``````20=2*2*5
``````

``````20=2(2)5(1)
``````

## Hint

N的大于sqrt(N)的质因子至多有一个。(sqrt(n)指N的开方取整)

## Sample Input

``````20
``````

## Sample Output

``````20=2(2)5(1)
``````

## FineArtz's solution

``````/* 分解质因数 */
#include <iostream>
#include <cmath>
#include <map>
using namespace std;

bool isp(int x){
for (int i = 2; i <= trunc(sqrt(x)); ++i)
if (x % i == 0) return false;
return true;
}

int main(){
int n;
cin >> n;
int nn = n;
map<int, int> ans;
for (int i = 2; i <= trunc(sqrt(nn)); ++i){
if (isp(i)){
while (n % i == 0){
++ans[i];
n /= i;
}
}
}
if (n != 1) ++ans[n];
cout << nn << "=";
for (map<int, int>::iterator i = ans.begin(); i != ans.end(); ++i)
cout << i->first << '(' << i->second << ')';
cout << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cmath"
using namespace std;

constexpr long long maxSize = 9999;

int main() {
int num, maxNum;
cin >> num;
maxNum = sqrt(num) + 1;

cout << num << "=";

//质因数个数
int ansNum = 0;

//集合
int ans[maxSize];
int ansn[maxSize];

//求解质因数
for (int i = 2; i <= maxNum; i++) {
if (num%i != 0)
continue;

//求解个数
int j;
for (j = 0; num%i == 0; j++) {
num /= i;
}

//记录数据
ans[ansNum] = i;
ansn[ansNum] = j;
ansNum++;
}

if (num != 1) {
ans[ansNum] = num;
ansn[ansNum] = 1;
ansNum++;
}

//输出
for (int i = 0; i < ansNum; i++) {
cout << ans[i] << "(" << ansn[i] << ")";
}

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

int main() {
int n;
cin >> n;

cout << n << '=';

for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
int tmp = 0;
while (n % i == 0) {
n /= i;
tmp++;
}
cout << i << '(' << tmp << ')';
}
}

if (n != 1) {
cout << n << '(' << 1 << ')';
}

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
using namespace std;

int main() {
long long n, _n;
cin >> n;
_n = n;
cout << n << "=";
for (int j = 2; j <= _n; j++) {
int cnt = 0;
while (n % j == 0) {
n /= j;
++cnt;
}
if (cnt != 0) {
cout << j << "(" << cnt << ")";
if (j * j >= _n) break;
}
if (n == 1) break;
}
cout << endl;
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstring>
#include <cmath>
bool b[50000];
int num[50000];
long n,i,j,temp;
int main(){
using namespace std;
memset(b,true,sizeof(b)); memset(num,0,sizeof(num));
cin>>n; b[1]=false; temp=n; cout<<n<<"=";
for (i=2; i<=50000; i++)
if (b[i]) for (j=2; j<=50000/i; j++) b[i*j]=false;
for (i=2; i<=sqrt(n); i++){
if ((b[i])&&(temp%i==0))
while (temp%i==0){
temp=temp/i; num[i]++;
}
}
for (i=2; i<=sqrt(n); i++)
if (num[i]) cout<<i<<"("<<num[i]<<")";
if (temp>1) cout<<temp<<"(1)";
return 0;
}
``````