✅ 题目简述

我们要在多个指定的区间 $[L, U]$ 中，统计：

1. 区间内的所有素数个数；
2. 其中可以写作 $p = a^2 + b^2$ 的素数个数。

根据费马定理（Fermat's theorem on sums of two squares），满足以下条件的奇素数 $p$ 可以写成两个整数平方的和：

• $p \equiv 1 \pmod{4}$

另外，$2 = 1^2 + 1^2$ 也符合该条件。

💡 示例输入输出说明

输入示例：

10 20
11 19
100 1000
-1 -1

输出示例：

10 20 4 2
11 19 4 2
100 1000 143 69

🧠 思路说明

1. 预处理素数：使用线性筛法生成所有 $[2, 10^6]$ 范围内的素数；

2. 处理每组输入区间 $[L, U]$：

   • 遍历所有预处理得到的素数；
   • 判断该素数是否在区间内；
   • 判断是否满足 $p = 4k + 1$ 或 $p = 2$；
   • 分别统计总数和平方和素数数目；

3. 输出格式严格遵循：L U x y

✅ 完整带注释的 C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

// 素数数组 a，合数标记数组 check，top 记录素数个数
int a[1100000], check[1100000], top;

// 线性筛法生成所有小于等于 10^6 的素数
void f() {
    top = 0;
    memset(check, 0, sizeof(check));
    for (int i = 2; i <= 1000000; i++) {
        if (!check[i]) a[top++] = i; // i 是素数，加入数组
        for (int j = 0; j < top; j++) {
            if (i * a[j] > 1000000) break; // 防止越界
            check[i * a[j]] = 1; // 标记为合数
            if (i % a[j] == 0) break; // 保证每个数只被最小素因子筛一次
        }
    }
}

int main() {
    f(); // 预处理素数

    int l, r;
    while (scanf("%d %d", &l, &r) != EOF) {
        if (l == -1 && r == -1) break; // 终止条件

        int total_primes = 0, sum_of_squares_primes = 0;

        for (int i = 0; i < top; i++) {
            if (a[i] > r) break; // 超出右边界，退出
            if (a[i] >= l) { // 素数在区间内
                total_primes++;
                // 若为 2 或 满足 p ≡ 1 (mod 4)，计入平方和素数
                if (a[i] == 2 || (a[i] - 1) % 4 == 0)
                    sum_of_squares_primes++;
            }
        }

        printf("%d %d %d %d\n", l, r, total_primes, sum_of_squares_primes);
    }

    return 0;
}

📌 复杂度分析

由于素数在 $10^6$ 内大约有 $7.8$ 万个，因此即使每组都遍历全部素数，也可在合理时间内完成。