HDU5317

題意:1つの数Kを定義、最小素因数形式はK=a*b*c形式(例えば12=2*2*3)であり、同じ1つだけ(したがって12は2,3の2つしか取ることができず、F[12]=2)はL,R区間に与えられ、区間内最大のF[x](L<=x<=R)を探し出す.
構想:まず素数表を打って、それから1000000内のすべての数を列挙して、可能な値は2,3,5,7,11,13,17の7つの数しかないので、arr配列は各数に対応する値の個数を格納して、それからdp配列で下のiとiのすべての数がjの値の個数を表すことができて、最後に与えられた2つの区間から1回の値の比較をすればいいです.

#include <stdio.h>
#include <iostream>
#define MAX 1000000+50
#define N 1000000
using namespace std;
int value[MAX],prime[MAX];
int dp[MAX][9];
void Isprime()
{
    int flag = 0;
    prime[2]=1;
    for(int i=3; i<=N; i++)
    {
        if(i%2==0)
            flag=1;
        else
            for(int j=3; j*j<=i; j=j+2)
                if(i%j==0)
                {
                    flag = 1;
                    break;
                }
        if(flag==0)
            prime[i]=1;
        flag=0;
    }
}
void getValue()
{
    for(int i = 2; i<=N; i++) //       ，        ，      value    1-1000000            
        if(prime[i])
            for(int j=i; j<=N; j+=i)
                value[j]++;
    // cout<<value[j]<<" ";
    // cout<<endl;
}
void solve()
{
    for(int i=2; i<=N; i++)
        dp[i][value[i]]++;  //   dp
    //for(int i = 2;i<=n;i++)
    //{
    //  cout<<dp[i][value[i]]<<" ";
    //}
    for(int i=2; i<=N; i++) //     ，      7    ，   dp   7       
        for(int j=1; j<8; j++)
            dp[i][j]+=dp[i-1][j];
    //if(i==99)
    //  for(int j = 1;j<8;j++)
    //    cout<<dp[i][j]<<" ";
}
void init()
{
    Isprime();
    getValue();
    solve();
}
int main()
{
    init();
    int T,i,j,L,R,flag;
    scanf("%d",&T);
    while(T--)
    {
        flag=-1;
        scanf("%d%d",&L,&R);
        for(j=2; j<8; j++) //j    7  
            if(dp[R][j]-dp[L-1][j]>=2)//dp    R      j   ，            j    ，          
                flag=max(flag,j);
        printf("%d
",flag);
    }
    return 0;
}