首页 > 代码库 > UVa 1644 (筛素数 + 二分) Prime Gap
UVa 1644 (筛素数 + 二分) Prime Gap
题意：
给出一个整数n，如果n是素数输出0，否则输出它后一个素数与前一个素数的差值。
分析：
首先用筛法把前十万个素数都筛出来，然后放到数组里。用二分找到不大于n的最大的素数的下标，如果这个素数等于n，则直接输出0，否则输出它后一个素数与它本身的差值。
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = 1299709; 5 const int maxp = 100000; 6 bool vis[maxn + 10]; 7 int prime[maxp + 10], cnt = 1; 8 9 void Init()10 {11 int m = sqrt(maxn + 0.5);12 for(int i = 2; i <= m; ++i) if(!vis[i])13 for(int j = i * i; j <= maxn; j += i)14 vis[j] = true;15 for(int i = 2; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i;16 }17 18 int main()19 {20 Init();21 int n;22 while(scanf("%d", &n) == 1 && n)23 {24 int L = 1, R = maxp;25 while(L < R)26 {27 int mid = L + (R - L + 1) / 2;28 if(prime[mid] <= n) L = mid;29 else R = mid - 1;30 }31 if(prime[L] == n) puts("0");32 else printf("%d\n", prime[L+1] - prime[L]);33 }34 35 return 0;36 }
UVa 1644 (筛素数 + 二分) Prime Gap
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。