根据质数的性质：$k \equiv 1\ (\bmod\ 4), k \in \mathbb P$（$2$ 为特例，需特判）可得以下代码：

AC code：

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> sieve(ll n) {
    vector<bool> is_p(n + 1, true);
    is_p[0] = is_p[1] = false;
    for (ll i = 2; i * i <= n; ++i) {
        if (is_p[i]) {
            for (ll j = i * i; j <= n; j += i) {
                is_p[j] = false;
            }
        }
    }
    vector<ll> res;
    for (ll i = 2; i <= n; ++i) {
        if (is_p[i]) {
            res.push_back(i);
        }
    }
    return res;
}

vector<bool> seg_sieve(ll L, ll R, const vector<ll>& primes) {
    vector<bool> is_p(R - L + 1, true);
    if (L == 1) {
        is_p[0] = false;
    }
    for (ll p : primes) {
        ll start = max(p * p, ((L + p - 1) / p) * p);
        if (start > R) {
            continue;
        }
        for (ll j = start; j <= R; j += p) {
            is_p[j - L] = false;
        }
    }
    return is_p;
}

int main() {
    ll l, r;
    cin >> l >> r;
    if (r < 2) {
        cout << 0 << endl;
        return 0;
    }
    ll sqrt_r = sqrt(r);
    vector<ll> primes = sieve(sqrt_r);
    vector<bool> is_p = seg_sieve(l, r, primes);
    int ans = 0;
    for (ll i = 0; i <= r - l; ++i) {
        if (is_p[i]) {
            ll num = l + i;
            if (num == 2) {
                ans++;
            } else if (num % 4 == 1) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Algo 1

分段打表即可。

Algo 2

o3-mini 给的分段筛：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long l, r;
    cin >> l >> r;
    
    // 如果 r < 2 则没有素数
    if(r < 2){
        cout << 0;
        return 0;
    }
    
    // 预筛出 2 ~ sqrt(r) 的素数
    long long lim = static_cast<long long>(sqrt(r)) + 1;
    vector<bool> isPrime(lim + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= lim; i++){
        if(isPrime[i]){
            for (int j = i * i; j <= lim; j += i)
                isPrime[j] = false;
        }
    }
    vector<int> basePrimes;
    for (int i = 2; i <= lim; i++){
        if(isPrime[i])
            basePrimes.push_back(i);
    }
    
    // 分段筛: 每段的长度可以设为 10^6
    const int segmentSize = 1000000;
    long long ans = 0;
    for(long long low = l; low <= r; low += segmentSize){
        long long high = min(low + segmentSize - 1, r);
        vector<bool> mark(high - low + 1, true);
        
        // 对每个预筛的素数 p，在 [low, high] 上标记 p 的倍数
        for (int p : basePrimes) {
            // 找到 [low, high] 内 p 的第一个倍数
            long long start = max((long long)p * p, ((low + p - 1) / p) * p);
            for(long long j = start; j <= high; j += p){
                mark[j - low] = false;
            }
        }
        // 特殊处理 1 不是素数
        if(low == 1)
            mark[0] = false;
        
        // 统计满足条件的素数
        for(long long i = 0; i < mark.size(); i++){
            if(mark[i]){
                long long num = low + i;
                // 根据数论，素数可以表示为两个正整数平方和当且仅当
                // num == 2 或 num % 4 == 1
                if(num == 2 || num % 4 == 1)
                    ans++;
            }
        }
    }
    
    cout << ans;
    return 0;
}

经典结论：一个奇素数能够表示为两个平方数的和，当且仅当这个素数模 $4$ 余 $1$。

特判 $2=1^2+1^2$ 后上线性筛直接硬冲即可。

#include <bits/stdc++.h>
using namespace std;
int pr[17000012], cnt = 0;
bitset<300000012> ppr;
int up;
int get()
{
    ppr[1] = true;
    for (int i = 2; i <= up; i++)
    {
        if (!ppr[i]) cnt++, pr[cnt] = i;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * pr[j] > up) break;
            ppr[i * pr[j]] = true;
            if (i % pr[j] == 0) break;
        }
    }
    return cnt;
}
int main()
{
    int l, r;
    cin >> l >> r;
    up = r;
    get();
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if ((pr[i] & 3) == 1 && pr[i] >= l && pr[i] <= r) ans++;
    if (l <= 2 && r >= 2) ans++;
    cout << ans << endl;
    return 0;
}