---
title: "分解质因数"
created: 2025-11-28
tags:
  - 算法
---

# 分解质因数

## 题目 [分解质因数](https://www.acwing.com/problem/content/description/869/)

![[image-fef710b7.png]]

## 思路分析

什么是分解质因数：

每个合数都可以写成几个质数相乘的形式 其中每个质数都是这个合数的因数 把一个合数用质因数相乘的形式表示出来 叫做分解质因数 也叫做分解质因子
如30=2×3×5 分解质因数只针对合数

根据算术基本定理

不考虑排列顺序的情况下 每个正整数都能够以唯一的方式表示成它的质因数的乘积 n=p1^a1 \* p2^a2 \* p3^a3…..pn^an

比如一个数16 在分解时先找到2这个质因子，然后由于16/2后还可以/2，所以会在2这个质因子上产生次方 不优化版本：从2~n 找到能整除的因子然后算次方

这里有个性质

x 的质因子最多只包含一个大于 根号x 的质数。如果有两个，这两个因子的乘积就会大于 x，矛盾。

i 从 2 遍历到 根号x。 用 x / i，如果余数为 0，则 i 是一个质因子。

s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 。

最后检查是否有大于 根号x 的质因子，如果有，输出。

**质因数的底数和指数： 底数指质数的基数 比如在分解12=2*****2*****3中 2和3就是底数 而指数是指底数出现的次数 2出现了两次 所以指数是2**

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

void divide(int x)

{

    for (int i = 2; i <= x / i; i ++ ){//i <= x / i:防止越界，速度快于 i < sqrt(x)

        if (x % i == 0){//i为底数

            int s = 0;//s为指数

            while (x % i == 0)

                x /= i, s ++ ;

            cout << i << ' ' << s << endl;//输出

        }

    }

    if (x > 1)

        cout << x << ' ' << 1 << endl;//如果x还有剩余，单独处理

    cout << endl;

}

int main()

{

    int n;

    cin >> n;

    while (n -- )

    {

        int x;

        cin >> x;

        divide(x);

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[x的因子链|x的因子链]] 🏠 [[00-刷题理模型]] ➡️ [[判断质数-素数|判断质数-素数]]