摘要：
意义：找出正整数L和U之间有多少个整数x满足x=pk的形式，其中p是质数，k˃1分析：首先筛选出1e6中的质数，枚举每个质数，找出满足1e12中条件的所有数字，然后对它们进行排序。对于L和U，用二分法找到小于U和L的最大数的下标，然后求差得到答案。
题意：
求正整数L和U之间有多少个整数x满足形如x=pk 这种形式，其中p为素数，k＞1
分析：
首先筛出1e6内的素数，枚举每个素数求出1e12内所有满足条件的数，然后排序。
对于L和U，二分查找出小于U和L的最大数的下标，作差即可得到答案。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 5 typedef long long LL; 6 7 const int maxn = 1000000; 8 const int maxp = 80000; 9 10 bool vis[maxn + 10]; 11 int prime[maxp], cntp = 0; 12 LL a[maxn], cnt = 1; 13 14 void Init() 15 { 16 int m = 1000; 17 for(int i = 2; i <= m; ++i) if(!vis[i]) 18 for(int j = i * i; j <= maxn; j += i) vis[j] = true; 19 for(int i = 2; i <= maxn; ++i) if(!vis[i]) prime[cntp++] = i; 20 21 for(int i = 0; i < cntp; ++i) 22 { 23 LL temp = (LL)prime[i] * prime[i]; 24 while(temp <= 1000000000000LL) 25 { 26 a[cnt++] = temp; 27 temp *= prime[i]; 28 } 29 } 30 std::sort(a, a + cnt); 31 } 32 33 int binary_search(LL n) 34 { 35 LL L = 0, R = cnt; 36 while(L < R) 37 { 38 LL mid = ((L + R + 1) >> 1); 39 if(a[mid] <= n) L = mid; 40 else R = mid - 1; 41 } 42 return L; 43 } 44 45 int main() 46 { 47 Init(); 48 int T; 49 scanf("%d", &T); 50 while(T--) 51 { 52 LL hehe, haha; 53 scanf("%lld%lld", &hehe, &haha); 54 int t = binary_search(hehe), k = binary_search(haha); 55 int ans = k - t; 56 if(a[t] == hehe) ans++; 57 printf("%d ", ans); 58 } 59 60 return 0; 61 }