給定n個正整數ai，將每個數分解質因數，并按照質因數從小到大的順序輸出每個質因數的底數和指數，
輸入格式
第一行包含整數n，
接下來n行，每行包含一個正整數aiai，
輸出格式
對于每個正整數aiai,按照從小到大的順序輸出其分解質因數后，每個質因數的底數和指數，每個底數和指數占一行，
每個正整數的質因數全部輸出完畢后，輸出一個空行，
資料范圍
1≤n≤1001≤n≤100,
1≤ai≤2?1091≤ai≤2?109
輸入樣例：
2
6
8
輸出樣例：
2 1
3 1
2 3
試除法求質因子
時間復雜度O(sqrt(n))
n中最多只包含一個大于sqrt(n)的質因子
代碼：
static void divide(int n){ for(int i=2;i<=n/i;i++){//n中最多只包含一個大于sqrt（n）的質因子，所以只列舉到sqrt（n）即可，大于的那個單獨處理 if(n%i==0){ int s=0; while(n%i==0){ n/=i; s++; } System.out.println(i+" "+s); } } if(n>1) System.out.println(n+" 1"); System.out.println(); }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95251.html
標籤：其他
上一篇：素數篩法（模板）
下一篇：唯一分解定理