这道题我们得用素数筛，到不是要判断某个数是否是质数，而是要在计算素数的过程中算出每一个数的最小质因数，对素数筛有这个功能！
首先我们看素数筛的步骤；
我们设计一个bool数组prime[N]，prime[i]=1时i为非素数，反之为素数；
我们从2开始遍历，终止条件是我们要判断的区间的右端点，即右端点为N；
1：如果prime[i]=0,即i是素数，我们进入循环
（1）从2*i开始，记为j，遍历到N，每次递增i，将这一过程的prime[j]记为1【因为这一过程中的j都是i的倍数，定然不是素数，所以prime[j]=1】
2：如果prime[i]=1，即不是素数，则continue；
这样一套下来，prime数组里记录的就是一个数是否是素数的信息了；
那么我们怎么在这个过程中找到一个数的最小质因子呢？可能有的人已经发现了，这个最小质因子就是对应的i，什么意思呢？意思是当prime[i]=0时，我们进入循环，其中所有遇到的数的最小质因数就是i了；
有了以上算法，我们就可以开始计算了；
#include<iostream>#include<algorithm>#include<vector>using namespace std;const int N=900010;bool prime[N+10];int mi[N];//mi[i]存储i的最小质因数int l,r;void getprime(){for(int i=2;i<=N;i++){//循环每一个数if(prime[i]) continue;//如果这个数不是素数，那么就跳过for(int j=i*2;j<=N;j+=i){//将所有素数的X倍都记为非素数prime[j]=1;mi[j]=i;//i是j的最小质因数}mi[i]=i;//质数的最小质因数是自己}mi[1]=1;//这里算不到1，所以得我们自己初始化}
那么接下来我们又遇到一个问题，我们怎么用以上信息将一个数质因数分解呢？
其实很简单，我们计算X时只需要进行以下循环即可；
首先我们有一个vector来存储答案，变量明为ans
1：如果X==1成立我们就退出循环
2：如果不成立我们进入以下操作
（1）将mi[X]push进ans
（2）X/=mi[X]即用X的最小质因数更新X
这么一套下来后ans里存储的就是X的质因数了；
接下来就是全套代码了；
/*** main函数返回值不能为void，否则会汇编出错，请使用int main(),并在最后return 0。* 虽然VC等windows下的编译器支持，但C/C++标准中不允许使用void main()!*/#include<iostream>#include<algorithm>#include<vector>using namespace std;const int N=900010;bool prime[N+10];int mi[N];int l,r;void getprime(){for(int i=2;i<=N;i++){if(prime[i]) continue;for(int j=i*2;j<=N;j+=i){prime[j]=1;mi[j]=i;}mi[i]=i;}mi[1]=1;}int main(){getprime();cin>>l>>r;//输入需要遍历的区间for(int i=l;i<=r;i++){vector<int> ans;int p=i;while(p!=1){ans.push_back(mi[p]);p/=mi[p];}cout<<i<<'=';sort(ans.begin(),ans.end());//将ans排个序for(int i=0;i<ans.size();i++){//输出anscout<<ans[i];if(i!=ans.size()-1) cout<<'*';}cout<<endl;}}
