题目描述
给定 $n$ 个正整数 $a_i$,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行,每行包含一个正整数 $a_i$。
输出格式
对于每个正整数 $a_i$,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
每个正整数的质因数全部输出完毕后,输出一个空行。
这道题的题目很好理解
意思是给定 $n$ 个正整数 $a_i$,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。
我们要注意:
质因数是要从小到大的顺序输出
每个质因数都要输出底数和指数。
说句人话就是:先输出拆成的数,再输出拆了多少个还有在每个正整数的质因数全部输出完毕后,输出一个空行(巨坑)
数据范围
$1≤n≤100$,
$2≤a_i≤2×10^9$
输入样例:
2
6
8
输出样例:
2 1
3 1
2 3
算法1
(数学计算) $O(n^2)$
额,我还是傻傻的讲一下模板吧
这道题很好做,但是不加优化还是过不了
下面是不推荐的几种做法:
一、不加优化
void divide(int n){
for(int i = 2;i <= n / i;i ++){
if(n % i == 0){ //如果可以整除i,那么就是n的因数
int s = 0; //i指数个数
while(n % i == 0){ //把n拆掉,看看有多少个i
n /= i; //拆掉
s ++; //指数增加
}
printf("%d %d\n",i,s); //输出i和s
}
}
if(n > 1) printf("%d %d\n",n,1); //如果n还没拆完,那么直接输出当前别拆好的n
printf("\n"); //注意:一定要输出空行,不然会死得很惨
}
好吧,$TLE$了,但是过了$6$个数据。
二、使用$sqrt$
如果您优化部分看不懂的话,可以先看一下我试除法判定质数的题解(逃
void divide(int n){
for(int i = 2;i <= sqrt(n);i ++){ //优化部分
if(n % i == 0){
int s = 0;
while(n % i == 0){
n /= i;
s ++;
}
printf("%d %d\n",i,s);
}
}
if(n > 1) printf("%d %d\n",n,1);
printf("\n");
}
离谱,过了…
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
int a[N];
void divide(int n){
for(int i = 2;i <= n / i;i ++){
if(n % i == 0){
int s = 0;
while(n % i == 0){
n /= i;
s ++;
}
printf("%d %d\n",i,s);
}
}
if(n > 1) printf("%d %d\n",n,1);
printf("\n");
}
int main(){
int n;
scanf("%d",&n);
while(n --){
int x;
scanf("%d",&x);
divide(x);
}
return 0;
}
原来我这个没写完啊