首页 > 代码库 > UVa 10539 (筛素数、二分查找) Almost Prime Numbers
UVa 10539 (筛素数、二分查找) Almost Prime Numbers
题意：
求正整数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\n", ans);58 }59 60 return 0;61 }
UVa 10539 (筛素数、二分查找) Almost Prime Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。