思路与算法

题面未规定X和Y大小顺序，先交换使较小端点在前。筛出不超过较大端点U的素数，然后扫描两个端点之间的闭区间并统计素数标记。

正确性说明

交换不改变两端点之间的闭区间。0和1排除，埃氏筛不会删素数，合数则被其不超过平方根的素因子删去，因此标记准确。最终循环恰好访问闭区间每个整数一次，且只对素数累加一，得到正确数量。

复杂度

初始化O(U)，筛表O(U log log U)，区间扫描O(U)，总时间O(U log log U)，额外空间O(U)。U不超过100000。

易错点

包含两个端点，端点相等也要处理；1不是素数；X大于Y须先规范化。本题端点可至10万且无顺序保证，不能直接复用千以内有序区间或大数窄区间的不同完整协议版本。

参考代码（C++11）

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int x, y;
    cin >> x >> y;
    if (x > y)
        swap(x, y);
    vector<bool> prime(y + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= y; ++i)
        if (prime[i])
            for (int j = i * i; j <= y; j += i)
                prime[j] = false;
    int count = 0;
    for (int i = x; i <= y; ++i)
        if (prime[i])
            ++count;
    cout << count << '\n';
}