Rockdu's Blog

题目背景

题目名称是吸引你点进来的

实际上该题还是很水的

题目描述

区间质数个数

输入输出格式

输入格式：

一行两个整数 询问次数n，范围m

接下来n行，每行两个整数 l,r 表示区间

输出格式：

对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line

输入输出样例

2 5
1 3
2 6

2
Crossing the line

说明

【数据范围和约定】

对于20%的数据 1<=n<=10 1<=m<=10

对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000

很裸的线性筛素数，再用一个数组维护前缀就行了。

#include<cstdio>
using namespace std;
const int maxn = 1e6 + 5;
int pri[maxn], m, n;
bool vis[maxn];
int sum[maxn];
void eu(int n) {
	vis[1] = 1;
	for(register int i = 2; i <= n; ++i) {
		if(!vis[i])	pri[++pri[0]] = i, sum[i] = sum[i - 1] + 1;
		else sum[i] = sum[i - 1];
		for(register int j = 1; i * pri[j] <= n && j <= pri[0]; ++j) {
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
}
int main() {
	scanf("%d%d", &m, &n);
	eu(n);
	int a, b;
	while(m--) {
		scanf("%d%d", &a, &b);
		if(a < 1 || b > n) {
			printf("Crossing the line\n");
			continue;
		}
		printf("%d\n", sum[b] - sum[a - 1]);
	}
	return 0;
}