因子分解

题目描述

输入整数 $n$ （ $2 \le n < 100$ ），输出其素因子分解表达式；素因子从小到大排列，指数为 1 时只写因子，大于 1 时写成 a^b。输入是一行整数 $n$ ，输出是一行表达式，相邻项用 * 连接。样例：输入 60，输出 2^2*3*5。

思路

从 $d=2$ 试除到 $\sqrt{n}$ ，除尽每个 $d$ 并统计指数；若剩余 $n>1$ 则补为指数 1 的素因子，再按规则拼接输出。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:37
# update_at: 2026-09-29 23:37

import sys


def factorize(n: int) -> list[tuple[int, int]]:
    """试除法分解 n：返回 (素因子, 指数) 列表，因子天然从小到大。"""
    factors: list[tuple[int, int]] = []
    d = 2
    while d * d <= n:  # 剩余的 n 若 >1，必然是一个素因子
        e = 0
        while n % d == 0:
            n //= d
            e += 1
        if e:
            factors.append((d, e))
        d += 1 if d == 2 else 2  # 2 之后只试奇数
    if n > 1:
        factors.append((n, 1))
    return factors


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    factors = factorize(n)
    # 输出表达式：指数为 1 时只写因子，否则写 a^b，用 * 连接
    print('*'.join(f'{p}^{e}' if e > 1 else str(p) for p, e in factors))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:37
 * update_at: 2026-10-05 05:37
 */

#include <iostream>
using namespace std;

typedef long long ll;

// 输出一项：指数为 1 时只写 p，否则写 p^e
void print_factor(ll p, int e) {
    cout << p;
    if (e > 1) cout << "^" << e;
}

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

    bool first = true;          // 控制 * 分隔符只在项之间出现
    for (ll d = 2; d * d <= n; ++d) { // 试到 sqrt(n)，剩余 >1 即素数
        if (n % d != 0) continue;
        int e = 0;
        while (n % d == 0) {    // 除尽 d，统计指数
            n /= d;
            ++e;
        }
        if (!first) cout << "*";
        print_factor(d, e);
        first = false;
    }
    if (n > 1) {                 // 收尾补剩余的素因子
        if (!first) cout << "*";
        print_factor(n, 1);
    }
    cout << "\n";
    return 0;
}

目录

题目描述

思路

参考代码