分解质因数

Love The Way You Lie 2022-10-22 04:12 213阅读 0赞

**上一篇博客：[质数的筛法][Link 1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  算数基本定理
 *  分解质因数
 *  优化方法
 *  例题
 *   *  题目描述
     *   *  输入格式
         *  输出格式
         *  数据范围
         *  输入样例
         *  输出样例
     *  题解
     *   *  解题代码

# 算数基本定理 #

在上一篇博客 [质数的筛法][Link 1] 中提到过算数基本定理。`算数基本定理` 也叫 `唯一分解定理`，主要的内容为：任何大于 **1** 的正整数都能 唯一 的分解为有限个质数的乘积。根据这一定理任何一个合数都可以被分解成几个质数相乘的形式。

# 分解质因数 #

把一个合数用质因数相乘的形式表示出来，叫做分解质因数。分解质因数可以使用 **试除法** 来分解，即从小到大枚举每一个数 **d**，如果 **d** 可以整除 **n**，则从 **n** 中除掉所有的因子 **d**，同时累计除去 **d** 的个数。通过唯一分解定理，可以知道一个合数的因子一定在扫描到这个合数之前就被其更小的质因子 **d** 除掉了，所以能整除 **n** 的一定是质数。

# 优化方法 #

通过分析可以得到一个合数 **n** 只可能有一个大于  n \\sqrt\{n\} n 的质因子，因为如果有两个的话，那么这两个质因子的乘积一定是大于 **n** 的。所以只需要从小到大枚举到  n \\sqrt\{n\} n ，最后判断 **n** 是否大于 **1** 即可，如果最后 **n > 1** 说明有一个大于  n \\sqrt\{n\} n 的质因子，那么将其输出即可，否则说明 **n** 已经被除尽，所有的质因子都已经求出。

# 例题 #

## 题目描述 ##

给定 **n** 个正整数 **ai**，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

### 输入格式 ###

第一行包含整数 **n**。

接下来 **n** 行，每行包含一个正整数 **ai**。

### 输出格式 ###

对于每个正整数 **ai**，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

### 数据范围 ###

**1 ≤ n ≤ 100,**  
**1 ≤ ai ≤ 2 × 109**

### 输入样例 ###

> **2  
> 6  
> 8**

### 输出样例 ###

> **2 1  
> 3 1**
> 
> **2 3**

**原题链接：[AcWing 867. 分解质因数][AcWing 867.]**

## 题解 ##

### 解题代码 ###

#include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    void divide(int n) { 
        for (int i = 2; i <= n / i; i++) { 
            if (n % i == 0) { 
                int s = 0;
                while (n % i == 0) { 
                    n /= i;
                    s++;
                }
                cout << i << ' ' << s << endl;
            }
        }
        if (n > 1) cout << n << ' ' << 1 << endl;
        puts("");
    }
    
    
    int main() { 
        int n;
        cin >> n;
        while (n--) { 
            int x;
            cin >> x;
            divide(x);
        }
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![20210326120556284.png][]

[Link 1]: https://ac-fun.blog.csdn.net/article/details/115395048
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 867.]: https://www.acwing.com/problem/content/869/
[20210326120556284.png]: /images/20221022/e71b05d6692e4e5c94173571f7f9a0dc.png