素数个数

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

const int N = 1e6 + 5;
ll n, m, pr[N], tot, s[N];
bool vis[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        memset(vis, 0, sizeof vis);
        ll total = m + 1;//将n到n+m的数全认为是质数，也就是这个区间上数的个数总数 
        //区间里数的总数减去该区间所有合数，最终就是质数个数 
        //下面开始找合数 
        for (ll i = 2; i <= 1e6 && i <= n + m; i++)//从2到1e6枚举因数 
        //因数枚举的范围2-1e6，i<=n+m是一个小剪枝 
            for (ll j = (n / i) * i; j <= n + m; j += i)//(n/i)*i最接近n的i的倍数 
            //j是枚举n到n+m之间i的倍数，他有i这个因子，所以他就是合数了，标记为访问过，防止重复访问 
                if (j >= n && j != i && !vis[j - n]){
                    //j>=n就排除了(n/i)*i<n的情况 
                    //j != i是因为，当i=j时，不足以证明他是合数 
                    vis[j - n] = 1;//标记为访问过 
                    total--;//找到一个合数，减掉该合数 
                }
        printf("%lld\n", total);
    }
}