---
title: "试除法求约数"
created: 2025-11-28
tags:
  - 算法
---

# 试除法求约数

## 题目 [试除法求约数](https://www.acwing.com/problem/content/871/)

![[image-857c13fe.png]]

## 思路分析

约数其实就是和质数反过来 能整除说明是约数

同样 因为是成对出现的 所以只需要枚举前半部分 后半部分可以通过n/i求出来

要注意 其实是有个if(i!=n/i)的逻辑在的 要去重  因为用的set 自动排序去重 所以代码中没体现出来

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

set<int> get_divisors(int n){

    set<int> res;

    for(int i=1;i<=n/i;i++){

        if(n%i==0){

            res.insert(i);

            res.insert(n/i);

        }

    }

    return res;

}

int main()

{

    int n;cin>>n;

    while(n--){

        int x;cin>>x;

        auto res=get_divisors(x);

        for(auto t:res)

            cout<<t<<" ";

        cout<<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[聪明的燕姿|聪明的燕姿]] 🏠 [[00-刷题理模型]] ➡️ [[轻拍牛头|轻拍牛头]]