哈理工第八届校团队赛热身C孪生素数猜想

题意：

Description

​ 素数只能被1和自身整除，孪生素数猜想为：存在无穷多个素数对形如（p, p + 2），如3和5， 11和13等

​ 先给定一个数k，判断k是否为孪生素数

Input

​ 输入第一行是t(t <= 100)，代表数据组数，接下来每组数据输入一个k(2 < k < 100000)

Output

​ 对于每组样例，请输出“Case x: y”, x是输入样例组数，如果是孪生数输出Yes，否则输出No

Sample Input

3

5

23

30

Sample Output

Case 1: Yes

Case 2: No

Case 3: No

思路：

​ 直接线性筛出1e5 + 2以内的全部素数，然后从素数中再筛选出全部的孪生素数并标记为1.直接判断book[k]是否为1，1Yes，0No

代码：

#include 
#include 
#define N 100002bool book[N + 5];
int prime[N + 5];void init() {memset(book, 0, sizeof(book));prime[0] = 0;for (int i = 2; i <= N; i++) {if (!book[i]) {prime[++prime[0]] = i;}for (int j = 1; j <= prime[0] && prime[j] * i <= N; j++) {book[prime[j] * i] = 1;if (i % prime[j] == 0) break;}}memset(book, 0, sizeof(book));for (int i = 2; i < prime[0]; i++) {if ((prime[i] - 2 == prime[i - 1]) || (prime[i] + 2 == prime[i + 1])) {book[prime[i]] = 1;}}if(prime[prime[0]] - 2 == prime[prime[0] - 1]) {book[prime[0]] = 1;}return;
}int main () {init();int T, k, tot = 0;scanf("%d", &T);while(T--) {scanf("%d", &k);if(book[k]) {printf("Case %d: Yes\n", ++tot);} else {printf("Case %d: No\n", ++tot);}}return 0;
}

转载请注明出处！！！

如果有写的不对或者不全面的地方 可通过主页的联系方式进行指正，谢谢

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！