【算法数学篇】试除法求约数

2025/7/22 19:17:51 来源：https://blog.csdn.net/2301_81170529/article/details/146967249 浏览: 次关键词：【算法数学篇】试除法求约数

题解：试除法求约数

题目传送门

869. 试除法求约数

一、题目描述

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

输入格式：

第一行包含整数 n
接下来 n 行，每行包含一个整数 aᵢ

输出格式：

共 n 行，其中第 i 行输出第 i 个整数 aᵢ 的所有约数

数据范围：

1 ≤ n ≤ 100
1 ≤ aᵢ ≤ 2×10⁹

二、题目分析

我们需要为每个给定的数 aᵢ 找出它的所有约数，并按升序排列输出。约数是指能整除该数的整数。

三、解题思路

使用试除法来高效地找出所有约数：

遍历从1到√aᵢ的所有整数
如果当前整数 i 能整除 aᵢ，则 i 和 aᵢ/i 都是约数
将找到的约数存入数组并排序后输出

四、算法讲解

试除法是求约数的经典方法：

对于数 a，我们只需要检查1到√a的范围
当发现 i 是约数时，同时记录 i 和 a/i（除非两者相同）
最后将所有约数排序输出

例子：
对于 a = 6：

检查1：6%1=0 → 记录1和6
检查2：6%2=0 → 记录2和3
不需要检查>√6≈2.45的数
得到约数1,2,3,6 → 排序后输出

五、代码实现

#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 110;
int n;
int a[N];void solve()
{cin >> n;while(n -- ){int a;cin >> a;vector<int> s; // 存储约数的动态数组// 试除法求约数for (int i = 1; i <= a / i; i ++) // 只需遍历到sqrt(a){if (a % i == 0) // 如果i是约数{s.push_back(i); // 加入iif (i != a / i) // 避免重复加入平方数的情况s.push_back(a / i); // 加入对应的另一个约数}}sort(s.begin(), s.end()); // 将约数排序// 输出结果for (int c : s)cout << c << " ";cout << "\n";}
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}