试除法求因数(约数)
2022/7/24 6:25:18
本文主要是介绍试除法求因数(约数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
试除法求约数
给定 \(n\) 个正整数 \(a\_i\),对于每个整数 \(a\_i\),请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行,每行包含一个整数 \(a\_i\)。
输出格式
输出共 \(n\) 行,其中第 \(i\) 行输出第 \(i\) 个整数 \(a\_i\) 的所有约数。
数据范围
\(1 \le n \le 100\),
\(2 \le a\_i \le 2 \times 10^9\)
输入样例:
2 6 8
输出样例:
1 2 3 6 1 2 4 8
想法
众所周知,约数 == 因数
一个数的因数是成对出现的,除了完全平方数以外
所以,如果一个数\(i\)可以整除数\(n\),那么\(n / i\)同样可以整除\(n\)
代码
#include <iostream> #include <algorithm> #include <vector> using namespace std; void get_d(int n) { vector<int> res; // 存储答案 for(int i = 1; i <= n / i; i++) // 枚举到√n即可,另一个大于√n的因数可以一次性推进res { if(n % i == 0) { res.push_back(i); if(i != n / i) res.push_back(n / i); // 完全平方数有两个因数相同,所以要判断一下 } } sort(res.begin(), res.end()); // 排序res for(auto temp : res) cout << temp << " "; // 遍历res输出 puts(""); return; } int main() { int n; cin >> n; while(n--) { int x; cin >> x; get_d(x); } return 0; }
这篇关于试除法求因数(约数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性