试除法求约数

• • • 一、思路
    • • • • （1）初始思路
          • （2）优化思路（时间复杂度降低为O(√n)）
    • 二、例题
    • • • • （1）题目
          • （2）输入格式
          • （3）输出格式
          • （4）代码（Java）

一、思路

假设要求n的所有约数

（1）初始思路

• 从前往后将所有小于等于n的数都枚举一遍，如果n可以被枚举到的数整除，那这个数就是n的约数

（2）优化思路（时间复杂度降低为O(√n)）

• 没有必要从前往后将所有小于等于n的数都枚举一遍
• 如果d是n的约数，则n/d必然也是n的约数（例如：12%3=0，12%4=0，12/3=4，则3和4都是12的约数）
• 可见约数都是成对出现的
• 故没有必要从前往后将所有小于等于n的数都枚举一遍
• 只需要将一对约数中较小的一个枚举出来，n除以较小的一个约数得到的自然就是较大的那个约数
• 枚举就可以从[1，n]缩减至[1，n/d]
• 但要注意一点：当n/d=d时，即一对约数是相同的数时，两个相同的约数会被重复录入（例如4*4=16，两个4会被当做两个不同的约数录入两次），而我们不希望出现这种重复
• 所以在录入较大的那个约数时需要进行一下判断，这个较大的约数和较小的约数是否相同，如果相同就不再重复录入

二、例题

（1）题目

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

（2）输入格式

• 第一行包含整数n。
• 接下来n行每行包含一个整数ai

（3）输出格式

• 输出共n行。其中第i行输出第i个整数ai的所有约数。

（4）代码（Java）

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] b = new int[n];for (int i = 0; i < n; i++) {b[i] = sc.nextInt();}for (int i = 0; i < n; i++) {ArrayList a = get_divisors(b[i]);for (int j = 0;j < a.size(); j++) {System.out.print(a.get(j) + " ");}System.out.println();}}//求约数public static ArrayList get_divisors(int n) {ArrayList a = new ArrayList<>();for (int i = 1; i <= n/i; i++) {if (n % i == 0){a.add(i);}//注意边界，避免重复：当n是i的平方时，若不加约束条件可能会重复录入//例如：当n=16 i=4时，若不加n/i!=i的条件，4就会被录入两次if (n/i != i){a.add(n/i);}}Collections.sort(a);//最后排序一下再输出return a;}
}