题目描述
给定 n 个正整数 ai,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
对于每个正整数 ai,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
每个正整数的质因数全部输出完毕后,输出一个空行。
样例
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例:
2
6
8
输出样例:
2 1
3 1
2 3
算法1
(暴力枚举) O(n2)
C++ 代码
#include <iostream>
using namespace std;
void get(int num){
for(int i = 2; i <= num ; ++i){
if(num % i ==0){ //此处时枚举num的每一个质因数,而不是合数。因为当枚举到i的时候,
//所有<=i的合数,都已经被分解过了,枚举到能够整除的i,一定是质数。
int cnt = 0;
while(num % i == 0){
++cnt;
num /= i;
}
cout<<i<<' '<<cnt<<endl;
}
}
}
int main(){
int n;
cin>>n;
while(n--){
int num = 0;
cin>>num;
get(num);
cout<<endl;
}
return 0;
}
算法2
(暴力枚举) O(sqrt(n))
C++ 代码
#include <iostream>
using namespace std;
void get(int num){
for(int i = 2; i <= num / i; ++i){ // i <= num / i; 一个数最多含有一个 > sqrt(num) 的质数。
//所以此处先处理 <=sqrt(num) 的质数
if(num % i ==0){
int cnt = 0;
while(num % i == 0){
++cnt;
num /= i;
}
cout<<i<<' '<<cnt<<endl;
}
}
if(num > 1) cout<<num<<' '<<'1'<<endl; //剩下的就是>=sqrt(num) 的质数
}
int main(){
int n;
cin>>n;
while(n--){
int num = 0;
cin>>num;
get(num);
cout<<endl;
}
return 0;
}