xtu 1279 Dual Prime

题目描述

如果一个合数x=p?q,p,q是素数且p≠q，我们称x是双素数。 现给你一个区间[a,b]，求区间内的的双素数个数。

输入

第一行是一个整数T(1≤T≤30000)，为样例的数目。 以后每行一个样例，为两个整数a,b(1≤a≤b≤106)

输出

依次每行输出一个样例的结果。

样例输入

3
1 10
1 100
1 1000000

样例输出

2
30
209867

AC代码

#include<stdio.h>
#define N 1000005
int a[N]={};
int f[N]={};
void init(){
	int i,j;
	a[0]=1,a[1]=1;
	//埃筛 
	for(i=2;i<N;i++){
		if(a[i]==0){
			for(j=2*i;j<N;j+=i){
				a[j]=1;
			}
		}
	}
	//计算f[i] 
	for(i=2;i<1005;i++){
	   if(a[i]==0){
	   	for(j=i+1;i*j<N;j++){
	   		if(a[j]==0){
	   			f[i*j]=1;
			   }
		}
	   }
	}
	//前缀和 
	for(i=0;i<N;i++){
		f[i]+=f[i-1];
	}
}
void sol(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",f[b]-f[a-1]);
}
int main()
{
	int T;
	scanf("%d",&T);
	init();
	while(T--){
		sol();
	}
 } 

解题思路：利用前缀和知识，满足条件为1，前缀和累计即可。