CodeForces 546D Soldier and Number Game（求素因子+前缀和）

题目大意：求(a!/b!)的所有质因数个数的总和
解题思路：
发现是把从1到5000000所有数的质因数全部都求出来，然后求一下前缀和，只要dp[a]-dp[b]（dp[i]就是i的质因数的个数）就是答案了。注意这里如果不用前缀和，而是直接这样求和的话也会超时。

#include<bits/stdc++.h>
#define maxn 5000010
using namespace std ;
typedef long long ll;
int n,t,a,b;
int dp[maxn],prime[maxn]; 
void init(){memset(prime,0,sizeof(prime));memset(dp,0,sizeof(dp));for(int i=2;i<=maxn;i++){if(prime[i]==0){                //dp[i]为合数 for(int j=i;j<=maxn;j+=i){int res=j;while(res%i==0){dp[j]++;res/=i;}prime[j]=1;}}}
}int main(){init();   //素数打表，从1-n打表for(int i=2;i<=maxn;i++)dp[i]=dp[i-1]+dp[i];    //计算前缀和 cin>>t;while(t--){scanf("%d%d",&a,&b);printf("%d\n",dp[a]-dp[b]);}return 0;
}