试除法求约数：深入分析与实践

矫情吗；* 2024-02-20 08:50 37阅读 0赞

## **试除法求约数：深入分析与实践** ##

在数学和算法领域，约数，也称因数，是一个非常基础的概念。给定一个整数，它的所有约数是能够整除它的数。例如，6 的约数包括 1、2、3 和 6。为了找到一个数的所有约数，一种常见的方法是试除法。本文将通过一个简单的 C++ 程序来探讨试除法如何工作。

#### **代码分析** ####

#include<bits/stdc++.h>
    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);
                if (i != n / i) res.push_back(n / i);
            }
        }
        stable_sort(res.begin(), res.end());
        return res;
    }

**核心思想**:

1.  遍历从 1 到 √n 的所有整数。这是因为如果 n 有一个大于 √n 的约数 d，那么必定存在一个小于或等于 √n 的约数 n/d。
2.  检查当前整数 i 是否可以整除 n。如果可以，i 和 n/i 都是 n 的约数。
3.  为了防止重复计数，当 i = n/i 时，只需要添加一次 i。这种情况只在 n 为完全平方数时发生。

**程序继续…**

int main()
    {
        
        int n;
        cin >> n;
        while (n --)
        {
        
            int a;
            cin >> a;
            auto res = get_divisors(a);
            for (auto t: res) cout << t << ' ';
            puts("");
        }
        return 0;
    }

该 `main` 函数首先读入一个数字 n，表示需要求约数的数字的数量。然后，程序对每个数字调用 `get_divisors` 函数，并将结果打印出来。

#### **优点和效率** ####

试除法是求约数问题中最直接的方法。它的时间复杂度是 O(√n)。虽然在某些情况下可能存在更高效的方法，但试除法因其简单性和普适性而广受欢迎。