Skip to content

11020: 【原1020】分解质因数

题目

题目描述

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

Description

每一个大于等于2的自然数,均可写成一个或多个质数的乘积,例如:

2=2

20=2*2*5

这种将一个整数分割成若干个质数之积的操作叫做分解质因数。现在,给你一个整数N,请你编写一个程序,对其分解质因数。

Input Format

输入为一行,正整数N,保证\( 1 < N < 2147483647 \)。

Output Format

输出N的质因数分解形式,格式为 N=P1(E1)P2(E2)P3(E3).... 其中,P1、P2、P3、……为组成N的各个质因子,

满足P1 < P2 < P3 < ...;E1、E2、E3、……分别为P1、P2、P3、……在N中的指数。

例如:

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;
}