1-2分解质因数

算法思想

1. 从小到大遍历
   1. 从2开始
2. 使用质数筛去和数
   1. 找到第一个质数 p，然后筛去 p 的所有倍数
3. 重复步骤2，直到 sqrt(n)
   1. 此时已经筛出了所有小质因数（小于等于 sqrt(n)的质因数）
4. 检查是否存在大质因数 2. 最多仅有一个（大于 sqrt(n)的质因数）

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 每个合数都可以写成几个质数相乘的形式，
        // 其中每个质数都是这个合数的因数，
        // 把一个合数用质因数相乘的形式表示出来，叫做分解质因数
        while(n -- > 0)
        {
            int a = sc.nextInt();
            divide(a);
        }
    }
    public static void divide(int x)
    {
        // 遍历找出小于等于 sqrt(n)的所有质数
        for(int i = 2; i <= x / i; i ++ )
        {
            // 若 i 是因数，i 一定是质因数；为什么
            // 这是实践规律，无需推导证明
            if(x % i == 0)
            {
                // 计算质因数 i 的指数
                int s = 0;
                while(x % i == 0)
                {
                    x /= i;
                    s ++;
                }
                System.out.println(i + " " + s + "");
            }
        }
        // 存在大于 sqrt(n)的质因数
        if(x > 1) System.out.println(x + " " + 1 + "");
        System.out.println();
    }
}