AcWing 867. 分解质因数
原题链接
简单
作者:
噗呲噗呲
,
2020-04-06 20:56:13
,
所有人可见
,
阅读 588
试除法分解质因数
#include <iostream>
using namespace std;
int n;
void divide(int x){
for(int i = 2; i <= x / i; i++){
if(x % i == 0){ // 这个地方是严格的从2 -- (i - 1) 一直整除上来的,已经除干净了,i 不可能再被 2 -- (i - 1)当中的数
int s = 0; // 整除,那么 x % i == 0 成立的话,i 必然是一个素数。
while(x % i == 0){
x /= i;
s++;
}
cout << i << " " << s << endl;
}
}
if(x > 1) cout << x << " " << 1 << endl;
}
int main(){
cin >> n;
while(n--){
int x;
cin >> x;
divide(x);
cout << endl;
}
return 0;
}