题目大意
小X是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的情感。小X认为，质数是一切自然数起源的地方。
在小X的认知里，质数是除了本身和$1$以外，没有其他因数的数字。
但由于小X对质数的热爱超乎寻常，所以小X同样喜欢那些虽然不是质数，但却是由两个质数相乘得来的数。
于是，我们定义，一个数是小X喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。
而现在，小X想要知道，在$L$到$R$之间，有多少数是他喜欢的数呢？
题目分析
在线性筛的时候顺带处理出是否是质数的乘积，最后做个前缀和。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=10000005;
int Prime[maxn],sum[maxn],cnt=0;
bool vst[maxn],Like[maxn];
void Table(int n) {
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Like[i]=1;
}
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
if(!vst[i])Like[i*Prime[j]]=1;
if(i%Prime[j]==0)break;
}
}
for(int i=1; i<=n; i++)sum[i]=sum[i-1]+Like[i];
}
int main() {
Table(10000000);
int t=Get_Int();
while(t--) {
int x=Get_Int(),y=Get_Int();
printf("%d\n",sum[y]-sum[x-1]);
}
return 0;
}
|
