请用 vector实现试除法求约数,要求按从小到大的次序输出 N的所有约数。 1<=N<=10^6。
时间: 2024-10-20 09:17:46 浏览: 11
gcd.rar_VHDL最大公约数_gcd
在C++中,我们可以使用`std::vector`来存储N的约数,并利用`std::set`的特点来保证约数的顺序,因为`std::set`自动维护元素的有序性。下面是一个简单的示例,演示如何使用`std::vector`和`std::set`来实现这个功能:
```cpp
#include <iostream>
#include <vector>
#include <set>
void trialDivision(int n) {
std::vector<int> divisors;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
// 添加较小的约数
divisors.push_back(i);
// 如果n是完全平方数,添加较大的约数也是原约数
if (i * i != n)
divisors.push_back(n / i);
}
}
// 使用set保持唯一性和排序
std::set<int> uniqueDivisors(divisors.begin(), divisors.end());
// 输出从小到大的约数
for (const auto& divisor : uniqueDivisors) {
std::cout << divisor << " ";
}
}
int main() {
int N;
std::cin >> N;
trialDivision(N);
return 0;
}
```
在这个程序中,我们首先遍历从1到`sqrt(n)`,找出所有的可能约数并加入`vector`。然后将`vector`转换为`std::set`,确保每个约数只出现一次并且自动保持升序。最后,我们逐个打印出约数。
阅读全文