求一个数的约数

方法1：试除法

869. 试除法求约数

给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n行，每行包含一个整数 ai。
输出格式
输出共 n行，其中第 i行输出第 i 个整数 ai 的所有约数。
数据范围
1≤n≤100
2≤ai≤2×109
输入样例：

2
6
8

输出样例：

1 2 3 6 
1 2 4 8

思路：

类似与质数判定
时间复杂度： O(sqrt(n))

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int a = sc.nextInt();
            //核心
            List<Integer> res = new ArrayList<>();
            for (int i = 1; i <= a / i; i++) {
                if (a % i == 0) {
                    res.add(i);
                    if (i != a / i) res.add(a / i);
                }
            }
            Collections.sort(res);
            for (int i : res) {
                System.out.print(i  + " ");
            }
            System.out.println();
        }
    }
}

方法2：算数基本定理 + 枚举

思路：

先对x进行质因数分解，然后枚举它所有的约数

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            List<Integer> res = new ArrayList<>();
            for (int i = 1; i <= n / i; i++) {
                if (n % i == 0) {
                    res.add(i);
                    if (n / i != i)
                        res.add(n / i);
                }
            }
            Collections.sort(res);
            for (int i = 0; i < res.size(); i++)
                System.out.print(res.get(i) + " ");
            System.out.println();
        }
    }
}