东华OJ-进阶题-10-分解质因数（C++）

• 问题描述
  求出区间[a,b]中所有整数的质因数分解。
• 输入说明
  输入两个整数a，b。

2<=a<=b<=10000

• 输出说明
  每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看范例)
• 输入范例

310

• 输出范例

3=34=2*25=56=2*37=78=2*2*29=3*310=2*5

感想：如果是合数的话，得分解到最后一个数是质数。
代码如下：

#include<bits/stdc++.h>usingnamespacestd;boolisPrime(intn){if(n<2)returnfalse;if(n==2)returntrue;if(n%2==0)returnfalse;for(inti=3;i*i<=n;i+=2)if(n%i==0)returnfalse;returntrue;}intmain(){inta,b;cin>>a>>b;for(inti=a;i<=b;++i){inttemp=i;if(isPrime(temp))cout<<temp<<"="<<temp;else{cout<<temp<<"=";boolsingle=true;for(intj=2;j*j<=i;++j){if(temp%j==0){if(!single)cout<<"*";cout<<j;temp=temp/j;j=1;single=false;if(isPrime(temp)){cout<<"*"<<temp;break;}}}}cout<<endl;}return0;}