#P1865. A % B Problem

    ID: 890 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>前缀和搜索素数判断质数筛法洛谷原创

A % B Problem

题目背景

题目名称是吸引你点进来的。
实际上该题还是很水的。

题目描述

给定 l,rl, r,求区间 [l,r][l, r] 内质数的个数。

输入格式

第一行有两个整数,分别代表询问次数 nn 和 给定区间的右端点最大值 mm

接下来 nn 行,每行两个整数 l,rl, r,代表一次查询。

输出格式

对于每次查询输出一行,若 l,r[1,m]l, r \in [1, m],则输出区间质数个数,否则输出 Crossing the line

2 5
1 3
2 6
2
Crossing the line

提示

数据范围与约定

  • 对于 20%20\% 的数据,保证 n,m10n,m\le 10
  • 对于 100%100\% 的数据,保证 1n10001\le n\le10001m1061\le m\le10^6109lr109-10^9\le l\le r\le 10^9