哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛） I

Prime

题解

T的值非常大，如果每一次都是重新寻找必定TLE。
所以这之前需要预处理。用数组n[i]记录 1~i 中质数的个数，那么[a,b]之间的质数的个数就等于n[b] - n[a-1]。
注意这里不能用n[b]-n[a-1]，否则会造成计数错误。例如a=5,b=6时，结果应为1，但是输出会是0。如果用n[b] - n[a] + 1，在a=8,b=9时会输出1，但结果应为0。
n[b] - n[a-1]的正确性可以自己证明一下。

AC代码

#include <bits/stdc++.h>//#pragma GCC optimize(2)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ull unsigned long long
#define ll long long
#define rep(i, x, y) for(int i=x;i<=y;i++)
#define mms(x, n) memset(x, n, sizeof(x))
#define pre(i, x, y) for(int i = x; i >=y; i--)
#define INF (0x3f3f3f3f)
#define mod (1e9+7)using namespace std;
const int N = 1e7 + 10;
int v[N],n[N];int main() {mms(v, 0);mms(n, 0);v[1] = 1;rep(i, 2, N) {if (!v[i]) {n[i] = n[i-1] + 1;for (int j =i * 2; j <= N; j+=i) v[j] = 1;} else n[i] = n[i-1];}int T;cin >> T;while(T--) {int a ,b;cin >> a >> b;cout << n[b]-n[a-1] << endl;}return 0;
}