Codefo 546D. Soldier and Number Game

题目链接：http://codeforces.com/problemset/problem/546/D

题意：输入a，b，n=a！/b！，求n 最多除以多少次变为1。

分析：相当于求n有多少个质因子。即求从b+1到a之间的数字质因子和为多少。

#include <iostream>
#include <cstring>
#include <cstdio>

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
",answer[a]-answer[b]);
    }

    return 0;
}