GESP1MONI02J2 区间里的孪生质数（25 分）

题目描述

质数（素数）是指大于 1，且除了 1 和它本身之外没有其他因数的正整数，例如 2、3、5、7、11。

如果两个质数相差 2，就称它们为一对孪生质数，例如 3 和 5、11 和 13 都是孪生质数。

现在给定一个区间 $[a, b]$，请你统计：

1. 区间 $[a, b]$ 内一共有多少个质数；
2. 区间 $[a, b]$ 内有多少对孪生质数——即满足 $p$ 和 $p + 2$ 都是质数，且两个数都落在 $[a, b]$ 内的数对 $(p, p + 2)$。

注意：像 17 和 19 这样的一对，只有当 19 也在区间内时才计入。

输入格式

输入一行，包含两个正整数 $a$ 和 $b$，用一个空格分隔，保证 $a \leq b$。

输出格式

输出共两行。

• 第一行一个整数，表示区间 $[a, b]$ 内质数的个数；
• 第二行一个整数，表示区间 $[a, b]$ 内孪生质数的对数。

样例 #1

样例输入 #1

1 10

样例输出 #1

4
2

样例解释

区间 [1, 10] 内的质数有 2、3、5、7，共 4 个；其中相差 2 的有 (3, 5) 和 (5, 7) 两对，因此输出 4 和 2。

样例 #2

样例输入 #2

14 18

样例输出 #2

1
0

样例解释

区间 [14, 18] 内只有 17 是质数，共 1 个；17 和 19 虽然相差 2，但 19 不在区间内，不能计入，所以孪生质数有 0 对。

数据范围

• $1 \leq a \leq b \leq 10^5$

本题共 10 个测试点，每个测试点 2.5 分，其中测试点 1、2 为题目给出的样例。

提示

把“判断质数”写成一个函数，再在主程序中两次使用它：

1. 写一个 bool isPrime(int x)：
   • $x < 2$（包括 1）不是质数；
   • 用 $d$ 从 2 开始试除，只要枚举到 $d \\times d \\leq x$（等价于 $d \\leq \\sqrt{x}$）即可；
   • 一旦某个 $d$ 能整除 $x$，立刻 return false（相当于 break）；
   • 循环结束都没有因数，返回 true。
2. 统计质数个数：用 for (int x = a; x <= b; x++) 扫描区间，若 isPrime(x) 则 cnt++。
3. 统计孪生质数对数：再扫一遍，但循环条件要写成 x + 2 <= b，保证 $p + 2$ 也在区间内；若 isPrime(x) && isPrime(x + 2) 则 pairs++。
4. 最后输出 cnt 与 pairs。

易错点：

• 第二问必须保证 $p + 2 \\leq b$，否则会多统计区间外的质数（如样例 2 中的 19）；
• 不要写成 isPrime(x) && isPrime(x + 1)，孪生质数相差的是 2；
• 本题数据范围内重复调用 isPrime 不会超时，若想更快，可以先用筛法把区间内的质数标记到 bool 数组中再统计。