分解质因数

把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。

867. 分解质因数
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：

2
6
8

输出样例：

2 1
3 1
2 3

理论

对于一个整数n，最多只包含一个大于sqrt(n)的质因子。
例如： 20 = 2 * 2 * 5 只有5是大于`sqrt(20) 的质因子

方法一

for循环从2~n-1，找到n的所有质因数
时间复杂度： O(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 x = sc.nextInt();
            divide(x);
        }
    }
    static void divide(int x) {
        if (x == 1) {
            System.out.println();
            return;
        }
        for (int i = 2; i <= x; i++) {
            if (x % i == 0) {
                int cnt = 0;
                while (x % i == 0) {
                    x /= i;
                    cnt++;
                }
                System.out.println(i + " " + cnt);
            }
        }
        System.out.println();
    }
}

方法二

根据我们的理论部分，可以优化循环部分
只用循环2~sqrt(n)部分即可，最后特判一下是不是大于 sqrt(n)
时间复杂度O(logn ~ 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 x = sc.nextInt();
            divide(x);
        }
    }
    static void divide(int x) {
        if (x == 1) {
            System.out.println();
            return;
        }
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                int cnt = 0;
                while (x % i == 0) {
                    x /= i;
                    cnt++;
                }
                System.out.println(i + " " + cnt);
            }
        }
        //特判
        if (x > 1) System.out.println(x + " " + 1);
        System.out.println();
    }
}

应用

1. 阶乘的分解

正难则反，直接考虑[1, x]不容易，可以考虑x以内的所有质数的次数，即数论中的含p量
考虑每个质数的一次，二次，。。。