题目描述

分解质因数

JAVA 代码

/**
 * 解题思路：
首先每个数字n最多只有一个大于n‾√n的质因子，
所以我们可以先使用n‾√n的时间复杂度
来看所有小于等于n‾√n的质数及它们的个数，
这里会有一个疑问就是怎么能保证i一定是质数？
这是因为当遍历到i的时候，由于n已经除完了i之前所有的质因子，
所以如果n可以整除i，那么i也就不能整除i之前的所有的质因子，
所以i一定为质数。
 */



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

class Main{

    static void divide(int n){
        //时间复杂度： o(n) --> o(sqrt(n))
        for(int i=2; i<=n/i; i++){
            int cnt = 0;//求质数的次数. 
            if(n%i==0){//一定为质因子
                while(n%i == 0){
                    cnt++;
                    n /= i;//是否能被再次整除. 
                }

                System.out.println(i + " " + cnt);
            }
        }
        //特判, 如果不是1那么就是那个较大的质因子.
        //最多只有一个大于sqrt(n)的质因子.
        if(n!=1)System.out.println(n + " "+ 1);
        System.out.println();
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(n-->0){

            divide(sc.nextInt());
        }
    }
}