题目描述

试除法 + 分解质因子

试除法 O(n根号a)

import java.util.*;
public class Main{
    static int calc(int x)
    {
        int res = 0;
        for (int i = 1; i <= x / i; i ++ )
            if (x % i == 0)
            {
                res ++ ;
                //如果 i != x/i 说明 x/i也是一个约数
                if (i != x / i) res ++ ;
            }

        return res;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while (n -- > 0)
        {
            int x = sc.nextInt();

            System.out.println(calc(x));
        }
    }
}

分解质因数法 O(n根号a)

import java.util.*;
public class Main{
    static int calc(int x)
    {
        int res = 1;

        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0)
            {
                int s = 0;
                while (x % i == 0){
                    x /= i; s ++ ;
                } 
                res *= (s + 1);
            }

        //还存在一个大于根号x的因子  res*(1 + 1)
        if (x > 1) res *= 2;

        return res;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while (n -- > 0)
        {
            int x = sc.nextInt();

            System.out.println(calc(x));
        }
    }
}