题意非常简单，就是给你一个区间（闭区间），然后让你统计区间内有多少数满足本身不是素数，但只有一个素因子
首先注意题目中区间左右端点最大可以取到1e12,这早就超越了int的表示范围
我们首先打表计算出1e6内的素数表，然后计算所有满足要求的数，存进数组，最后排序
然后对于给定的区间[L,R],我们用二分找到上界和下届
二分一直是我心中的痛，总是用不好，以后碰一道二分记录一道
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iomanip> #include<assert.h> #include<vector> #include<list> #include<map> #include<set> #include<sstream> #include<stack> #include<queue> #include<string> #include<bitset> #include<algorithm> #pragma warning(disable:4996) #define me(s) memset(s,0,sizeof(s)) #define _for(i,a,b) for(int i=(a);i<(b);++i) #define _rep(i,a,b) for(int i=(a);i<=(b);++i) using namespace std; typedef pair <int, int> pii; typedef long long ll; typedef unsigned long long llu; const int inf = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const double eps = 1e-15; const int maxn = 1000000; ll p[maxn + 5], vis[maxn + 5], pcnt; vector<ll> ans; void init() { me(vis); pcnt = 0; for (int i = 2; i<maxn; i++) { if (!vis[i]) { p[pcnt++] = i; for (int j = 2; i*j < maxn; j++) vis[i*j] = true; } } for (int i = 0; i<pcnt; i++) { ll tmp = p[i] * p[i];//刚开始没用p数组没用ll坑死 while (tmp < 1000000000000LL) { ans.push_back(tmp); tmp *= p[i]; } } sort(ans.begin(), ans.end()); } ll L, R; int main() { init(); int T; scanf("%d", &T); while (T--) { scanf("%lld%lld", &L, &R); cout << lower_bound(ans.begin(), ans.end(), R+1) - lower_bound(ans.begin(), ans.end(), L) << endl; } }