HDU 5317 RGCDQ

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5317

题意：一个数n可以分解成若干个质数相乘的等式(如12=2*2*3有2个不同的质数，10=2*5有2个不同的质数)，那么我们认为f(12)=2,f(10)=2，求gcd(f[L],f[R])

思路：1<= L,R <= 1000000，2*3*5*7*11*13*17*19大于1000000，因此最多有7种质数，f[x]<=7，我们用素数筛法可以预处理出1000000以内所有数的f[x]，然后处理所有的情况就可以了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 1000000
using namespace std;

int prime[maxn+30],num[maxn+30][10];

void init()
{
    memset(num,0,sizeof(num));
    memset(prime,0,sizeof(prime));
    for (int i=2;i<=maxn;i++)
    {
        if (!prime[i])
        {
            for (int j=i*2;j<=maxn;j+=i)
            {
                prime[j]++;
            }
        }
    }

    for (int i=2;i<=maxn;i++)
    {
        for (int j=1;j<=7;j++)
         num[i][j]=num[i-1][j];
        num[i][prime[i]]++;
    }
}

int main()
{
    init();
    int t,l,r;
    scanf("%d",&t);
    while (t--)
    {
        int tmp[10];
        scanf("%d%d",&l,&r);
        for (int i=1;i<=7;i++)
        {
            tmp[i]=num[r][i]-num[l-1][i];
        }

        int res;
        if (tmp[7]>=2)
            res=7;
        else if (tmp[6]>=2)
            res=6;
        else if (tmp[5]>=2)
            res=5;
        else if (tmp[4]>=2)
            res=4;
        else if (tmp[3]>=2 || tmp[6] && tmp[2])
            res=3;
        else if (tmp[2]>=2 || (tmp[6] && tmp[3]) || (tmp[4] && tmp[2]))
            res=2;
        else
            res=1;

        printf("%d\n",res);

    }
}