1099 性感素数 （20 分）
“性感素数”是指形如 (p, p+6) 这样的一对素数。之所以叫这个名字，是因为拉丁语管“六”叫“sex”（即英语的“性感”）。（原文摘自 http://mathworld.wolfram.com/SexyPrimes.html）
现给定一个整数，请你判断其是否为一个性感素数。
输入格式：
输入在一行中给出一个正整数 N (≤108)。
输出格式：
若 N 是一个性感素数，则在一行中输出 Yes，并在第二行输出与 N 配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。若 N 不是性感素数，则在一行中输出 No，然后在第二行输出大于 N 的最小性感素数。
输入样例 1：
输出样例 1：
输入样例 2：
输出样例 2：
代码实现:
这个题不是最难的一道题,但却是我用时最长的一道题,好像有3分没通过,当时一直找来着没找出来哪儿有问题,明白这代码有点傻,但是毕竟是考试的时候写出来的,贴了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<iostream>using namespace std;bool isPrime(int n){if(n<=0||n==1) return false;if(n==2) return true;for(int i = 2;i*i<=n;i++){if(n%i==0) return false;}return true;
}
int main(){int n;cin>>n;if(isPrime(n)&&isPrime(n-6)){cout<<"Yes"<<endl;cout<<n-6;return 0;}if(isPrime(n)&&isPrime(n+6)){cout<<"Yes"<<endl;cout<<n;return 0;}cout<<"No"<<endl;for(int i = n;i<100000001;i++){if(isPrime(i)&&isPrime(i-6)){cout<<i;return 0;}if(isPrime(i)&&isPrime(i+6)){cout<<i;return 0;}}return 0;
}
|
满分代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <iostream>
#include <algorithm>
using namespace std;bool is_prime(int x){if(x<=1)return false;for(int i=2;i*i<=x;++i){if(x%i==0)return false;}return true;
}int main() {int N;cin>>N;bool ans_s=is_prime(N-6);bool ans_b=is_prime(N+6);if(is_prime(N)&&(ans_s||ans_b)){cout<<"Yes"<<endl;if(ans_s)cout<<N-6;else cout<<N+6;}else{for(int i=N+1;;++i){ans_s=is_prime(i-6);ans_b=is_prime(i+6);if(is_prime(i)&&(ans_s||ans_b)){cout<<"No"<<endl;cout<<i;return 0;}}}return 0;
}
|
