[蓝桥杯][基础训练]分解质因数

Description

求出区间[a,b]中所有整数的质因数分解。

Input

输入两个整数a，b。

Output

每行输出一个数的分解，形如k=a1*a2*a3...(a1≤a2≤a3...，k也是从小到大的)(具体可看样例)。

Sample Input

3 10

Sample Output

3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

 1 #include<iostream>
 2 #include<vector>
 3 #include<cmath>
 4 using namespace std;
 5 int n,m;
 6 vector<int> ans;
 7 int check(int x){//检查是否为素数 
 8     for(int i=2;i<=sqrt(x);i++){
 9         if(x%i==0)
10             return 0;
11     }
12     return 1;
13 }
14 void dfs(int x){
15     if(x==1){//如果质因数都分解完了，就把质因数都输出 
16         for(int i=0;i<ans.size();i++){
17             if(i==ans.size()-1)
18                 printf("%d
",ans[i]);//最后一个不加*号 
19             else
20                 printf("%d*",ans[i]);    
21         }
22     }
23     for(int i=2;i<=x;i++){
24         if(x%i==0&&check(i)){//如果既是质数又是因数，就选它 
25             ans.push_back(i);
26             dfs(x/i);//将x/i继续搜索质因数 
27             break;
28         }
29     }
30 }
31 int main(){
32     scanf("%d%d",&n,&m);
33     for(int i=n;i<=m;i++){
34         ans.clear();
35         if(i==1){
36             printf("1=1");
37         }
38         printf("%d=",i);
39         dfs(i);
40     } 
41     return 0;
42 }

　　dfs函数这里，只有递归没有回溯。因为刚好从小到大去找质因数就一定是最优解。就不用回溯来判断所有解了

找素数的函数还可以继续优化