题目描述

试除法求约数 -

时间复杂度

O(sqrt(n))

JAVA 代码

import java.io.*;
import java.util.*;

class Main{
    static void get_divisor(int x){
        //TreeSet 是二差树实现的,Treeset中的数据是自动排好序的,不允许放入null值
        Set<Integer> s = new TreeSet<Integer>();

        for(int i=1; i<=x/i; i++){
            //如果是约数.
            if(x%i==0){
                s.add(i);
                //得到另一个约数
                if(x/i!=i) s.add(x/i);//如果x/i = i 那么只放一次. 
            }
        }
        for(Integer cur: s){
            System.out.print(cur+" ");
        }
        System.out.println();
    }

    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        while(n-->0){
            int num = Integer.parseInt(in.readLine());
            get_divisor(num);
        }
    }
}