//这个很好了。。。虽然是一般。。

int isp[1000100];

int p[1000100];

void init()

{

    int sum=0;

    int i,j;

    fill(isp,isp+1000007,true);

    for(i=2;i<=1000000;i++)

    {

        sum++;

        if(!isp[i]) continue;

        for(j=i+i;j<=1000000;j+=i)

        {

            sum++;

            isp[j]=false;

        }

    }

    int num=0;

    for(i=2;i<=1000000;i++)

        if(isp[i])

            p[++num]=i;

}

题意：

F（x）:对于x的素数因子的种类个数。

给t(<=1e6)个查询，每个查询给出L,R(<=1e6),求在区间[L,R]内求一个maxGCD（F(i),F(j)）

F（i）肯定<7；

思路：

计数一下，然后后面直接搞；

用sum数组表示从1->i有数量j的个数。

最终他的个数有>=2的话可以，或者还有一种情况就是6/2或者6/3的最大公约数是2/3.后面就是手动枚举了一下。

其实弱学到的最好的就是这个线性搞出一个素数因子表。

#include <iostream>

#include <algorithm>

#include <stdio.h>

using namespace std;

bool isPrime[1000001];

int cnt[1000001];

int sum[1000001][8];

void Init()

{

    fill(isPrime, isPrime + 1000001, true);

    for(int i = 2; i <= 1000000; ++i)

    {

        if(!isPrime[i])

            continue;

        ++cnt[i];

        for(int j = i + i; j <= 1000000; j += i)

        {

            isPrime[j] = false;

            ++cnt[j];

        }

    }

    for(int i = 2; i <= 1000000; ++i)

        for(int j = 1; j <= 7; ++j)

            sum[i][j] = sum[i - 1][j] + (cnt[i] == j ? 1 : 0);

}

int main()

{

    Init();

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int l, r;

        scanf("%d%d", &l, &r);

        int cnt[8] = {0};

        for(int i = 1; i <= 7; ++i)

            cnt[i] = sum[r][i] - sum[l - 1][i];

        if(cnt[7] >= 2)

            printf("7\n");

        else if(cnt[6] >= 2)

            printf("6\n");

        else if(cnt[5] >= 2)

            printf("5\n");

        else if(cnt[4] >= 2)

            printf("4\n");

        else if(cnt[3] >= 2 || (cnt[3] && cnt[6]))

            printf("3\n");

        else if(cnt[2] >= 2 ||

                (cnt[2] && cnt[4]) ||

                (cnt[2] && cnt[6]) ||

                (cnt[4] && cnt[6]))

            printf("2\n");

        else

            printf("1\n");

    }

    return 0;

}

/*1 2 3 4 5 6 7*/

/*

7     7 7

6     6 6

5     5 5

4     4 4

3     3 3 3 6

2     2 2 2 4 2 6 4 6

*/