//这个很好了。。。虽然是一般。。
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
*/
