资源限制：
时间限制：1.0s 内存限制：512.0MB
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1a2a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先筛出所有素数，然后再分解。
数据规模和约定
2<=a<=b<=10000
思路：
用dfs
代码：
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int n,m;
vector<int> ans;
int check(int x){//检查是否为素数
for(int i=2;i<=sqrt(x);i++){
if(x%i==0)
return 0;
}
return 1;
}
void dfs(int x){
if(x==1){//如果质因数都分解完了，就把质因数都输出
for(int i=0;i<ans.size();i++){
if(i==ans.size()-1)
printf("%d\n",ans[i]);//最后一个不加*号
else
printf("%d*",ans[i]);
}
}
for(int i=2;i<=x;i++){
if(x%i==0&&check(i)){//如果既是质数又是因数，就选它
ans.push_back(i);
dfs(x/i);//将x/i继续搜索质因数
break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=n;i<=m;i++){
ans.clear();
if(i==1){
printf("1=1");
cout<<endl;
}
else
{
printf("%d=",i);
dfs(i);
}
}
return 0;
}
image.png
