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，前缀和累计即可。