Acwing---869. 试除法求约数

1.题目

给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。

输入格式
第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个整数 $ai$。

输出格式
输出共 $n$ 行，其中第 $i$ 行输出第 $i$ 个整数 $ai$ 的所有约数。

数据范围
$1\le n\le 100,$

$1\le ai\le 2\times 10^9$

输入样例：

2
2
6

输出样例：

1 2 3 6
1 2 4 8

2.基本思想

思路

• 什么是约数：如果一个数a除以另一个数b的余数为0，即 a%b == 0, 则b是a的约数。

如何求一个数x的所有约数：

• 用 x 除以 1 到 x 的所有数，如果余数是0，则把除数加到答案中。

可以优化吗？

• 如果 a / b = c···0，则一定有 a % c = b····0。所以一个数 x 的约数肯定是成对存在的，对称轴是 根号x。
• 因此，只需要用 x 除以 1 到 根号x 之间的数，如果余数是0，则把除数以及x / 除数加到答案中。

3.代码实现

import java.util.*;

public class _869试除法判定约数 {
   
    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
   
            int ai = sc.nextInt();
            is_divid(ai);
            System.out.println();
        }
    }

    private static void is_divid(int n) {
   
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n / i; i++) {
   
            if (n % i == 0) {
   
                list.add(i);
                if (n / i != i) list.add(n / i);//特判 3*3=9 这种 只加入一次
            }
        }
        Collections.sort(list);
        for (int i : list) System.out.print(i + " ");
    }
}