解题思路： 一、先用筛法生成质数列表prime[]，以及f[i]标记（含义：i是不是合数），并且生成质数索引p_idx[i]（含义：i是第几个质数，如果i自己不是质数则它前面的质数是第几个），方便后面快速统计区间内的质数个数，R的索引减L的索引即可。 二、同时每找到一个新的质数，都与已找到的质数（prime[]中的所有含刚找到的质数）相乘，生成z[t]标记（t是不是两个质数的积）。 三、最后做一个循环，根据质数积标记z[t]，生成质数积索引z_idx[i]（含义：i是第几个质数积，如果i自己不是质数积则它前面的质数积是第几个）。 四、读入各组区间数据，根据L、R的p_idx索引和z_idx索引值直接推算出区间内共有多少个小X喜欢的数。计算时要注意区分L是不是质数（或质数积）的情形。 五、结论：曾经想过用筛法生成质数列表（6.6万）、质数积列表(190万）后， 用二分法查询起止L、R在这两个列表的位置。但似乎比较耗时，一来质数积列表生成时是无序的，要先排序， 时间复杂度190万log(190万）=310^7;二来有10^5组数据，每组要对两个列表各查2次，时间复杂度10^5 * 2* (log(6.6万）+log(190万）)=6*10^6。 所以最后还是用了提前生成索引的方法，质数列表索引不用额外增加时间复杂度，生成质数积列表索引增加10^7。还是比较划算的。 更简单做法是线性筛。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+2; 
int q,l,r,ma=N,pcnt,zcnt;
bool f[N],z[N];//f[i]==1:i是合数，z[i]==1:i是两个质数的积 
int prime[N],z_idx[N],p_idx[N];//p_idx某个质数是第几个 
int main(){
	for(int i=2;i<=ma;i++){		
		if(f[i]==0){
			prime[pcnt++]=i;
			p_idx[i]=pcnt;			
			for(long long j=(long long)i*i;j<=ma;j+=i)	f[j]=1;				
			for(int k=0;k<pcnt;k++){//新质数乘以已知质数（含自己），加入到zhi质数积数组 
				long long t=(long long)i*prime[k];
				if(t<=ma) z[t]=1;
				else break;
			}			
		}
		p_idx[i]=pcnt;//i是第几个质数，如果i自己不是质数则i前面的质数是第几个 		
	}
	for(int i=2;i<=ma;i++){ //生成z的索引 
		if(z[i]) zcnt++; 
		z_idx[i]=zcnt;
	}	
	cin>>q;		
	for(int i=0;i<q;i++){
		scanf("%d%d",&l,&r);
		if(l<2)l=2;
		printf("%d\n",p_idx[r]-p_idx[l]+!f[l]+z_idx[r]-z_idx[l]+z[l]);
	}
}