试除法求数的约数

一时失言乱红尘 2022-11-18 01:26 184阅读 0赞

**上一篇博客：[分解质因数][Link 1]**

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

### 文章目录 ###

*  定义
 *  试除法求约数
 *  例题
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  数据范围
         *  输入样例
         *  输出样例
     *  解题代码

# 定义 #

若整数 **n** 除以整数 **d** 的余数为 **0**，即 **d** 能整除 **n** ，则称 **d** 是 **n** 的约数，**n** 是 **d** 的倍数，记为 **d|n**。

# 试除法求约数 #

从 **1 ~ n** 依次枚举试除每一个数，判断该数是否可以整除 **n**，如果可以整除 **n**，说明该数是 **n** 的约数。试除法还可以优化一下，即我们可以发现约数都是 `成对出现` 的，如果 **d** 可以整除 **n**，那么 **n / d** 也可以整除 **n**。我们假设 **d** 与 **n / d** 中 **d** 是较小的那一个，那么 **d <= n / d** 即 **d <=  n \\sqrt\{n\} n**。所以只需要枚举到  n \\sqrt\{n\} n 即可。

当求另一个数的时候要注意判断一下 **d** 与 **n / d** 是否相等，因为 **d** 也可能是 **n** 的平方根，如果相等那么只记录一次即可。

# 例题 #

## 题目信息 ##

### 题目描述 ###

给定 **n** 个正整数 **ai**，对于每个整数 **ai**，请你按照从小到大的顺序输出它的所有约数。

### 输入格式 ###

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

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

### 输出格式 ###

输出共 **n** 行，其中第 **i** 行输出第 **i** 个整数 **ai** 的所有约数。

### 数据范围 ###

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

### 输入样例 ###

> **2  
> 6  
> 8**

### 输出样例 ###

> **1 2 3 6  
> 1 2 4 8**

题目来源：[AcWing 869. 试除法求约数][AcWing 869.]

## 解题代码 ##

#include<iostream>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    vector<int> get_divisors(int n) { 
        vector<int> res;
        for (int i = 1; i <= n / i; i++) { 
            if (n % i == 0) { 
                res.push_back(i);
                // 判断一下 i 是否是 n 的平方根，如果不是那么将其加入到 vector 中
                if (i != n / i) res.push_back(n / i);
            }
        }
        // 将结果集进行排序，从小到大输出
        sort(res.begin(), res.end());
        return res;
    }
    
    int main() { 
        int n;
        cin >> n;
        while (n--) { 
            int x;
            cin >> x;
            auto ans = get_divisors(x);
            for (auto i : ans) cout << i << ' ';
            cout << endl;
        }
        return 0;
    }

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

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

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