题意：输入a，b，n=a！/b！，求n 最多除以多少次变为1。
分析：相当于求n有多少个质因子。即求从b+1到a之间的数字质因子和为多少。
#include#include #include using namespace std;int v[5000005];//v[i]记录i是否为质数int prime[50000];//素数表int num;int mini[5000005];//mini[i]表示i的最小质因子。int ans[5000005];//ans[i]表示i有多少个质因子。int answer[5000005];//answer[i]表示从1到i共有多少个质因子void init(){ memset(v,0,sizeof(v)); num=0; for(int i=2;i<=5000000;i++) mini[i]=i; for(int i=2;i<=5000000;i++) { if(v[i]==0) { prime[++num]=i; } for(int j=1;j<=num&&i*prime[j]<=5000000;j++) { int t=i*prime[j]; v[t]=1; if(mini[t]>prime[j]) mini[t]=prime[j]; } } ans[2]=1; for(int i=3;i<=5000000;i++) { ans[i]=ans[i/mini[i]]+1;//ans[i]为i除以他的最小质因子的质因子数加上1 } answer[1]=0; for(int i=2;i<=5000000;i++) { answer[i]=answer[i-1]+ans[i]; }}int main(){ int t,a,b; scanf("%d",&t); init(); while(t--) { scanf("%d%d",&a,&b); printf("%d\n",answer[a]-answer[b]); } return 0;}