# [TIOJ 1668 . 分組編隊](https://tioj.ck.tp.edu.tw/problems/1668)題解
這題看起來套個質數篩就篩完了，但是他的範圍很大($2{\leq}l{\leq}r{\leq}2147483647$)，直接篩肯定會燒雞，所以必須只篩區間$[l,r]$的質數。可以發現只需要先預處理$\sqrt{2147483647}$以內的質數，然後拿這些質數去把$[l,r]$內不是質數的數篩掉，在一個數第一次被篩掉的時候更新答案。
:::spoiler AC扣(更新:rejudge之後他爛了(再更新:我發現我solve()裡的x會溢位造成TLE))

#include <iostream>
#include <bitset>
#define int long long
using namespace std;

const int sq = 50000;
int primes[25001], pcnt, ans, t, l, r;
bitset<50001> _np;

inline void init() {
    primes[pcnt++] = 2;
    for (int i = 3; i <= sq; i += 2) {
        if (_np[i >> 1]) continue;
        primes[pcnt++] = i;
        if (i > 500) continue;
        for (int j = i * i; j <= sq; j += (i << 1)) {
            _np[j >> 1] = 1;
        }
    }
}

inline void solve(int l, int r) {
    ans = r - l + 1;
    bitset<200001> np;
    for (int i = 0; (i < pcnt) && (primes[i] * primes[i] <= r); i++) {
        for (int x = (l / primes[i]) * primes[i]; x <= r; x += primes[i]) {
            if (x < l || x == primes[i] || np[x - l]) continue;
            --ans;
            np[x - l] = 1;
        }
    }
    cout << ans << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    init();
    cin >> t;
    while (t--) {
        cin >> l >> r;
        solve(l, r);
    }
    return 0;
}

:::