题目
“性感素数 ”是指形如 (p,p+6) 这样的一对素数。
之所以叫这个名字，是因为拉丁语管“六”叫“sex”（即英语的“性感”）。
现给定一个整数，请你判断其是否为一个性感素数。
输入格式
输入在一行中给出一个正整数 NN。
输出格式
若 N 是一个性感素数，则在一行中输出 Yes，并在第二行输出与 N 配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。
若 N 不是性感素数，则在一行中输出 No，然后在第二行输出大于 N 的最小性感素数。
数据范围
1≤N≤108
输入样例1：
输出样例1：
输入样例2：
输出样例2：
笔者解析
本题运用了经典求素数的方法求解，使用的判断素数算法模板如下
1
2
3
4
5
6
7
| public static boolean prime (int num){
if(num<=1){return false;}
for (int i = 2; i <= num/i; i++) {
if(num%i == 0){return false;}
}
return true;
}
|
本题的可能情况有一下几种
- 输入的数据num是素数，当num-6是素数，则输出num-6
- 输入的数据num是素数，当num-6是不素数，但num+6是素数，则输出num+6
- 输入的数据num不是素数，则开始不断加1，知道找到符合情况1或情况2数字，输出这个数
代码
笔者java代码
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
| import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
boolean a = prime(n-6);
if(prime(n)&&(a||prime(n+6))){
System.out.println("Yes");
if(a){
System.out.println(n-6);
}else {
System.out.println(n+6);
}
}else {
System.out.println("No");
while (true){
n++;
a=prime(n-6);
if(prime(n)&&(a||prime(n+6))){
System.out.println(n);
break;
}
}
}
}
public static boolean prime (int num){
if(num<=1){return false;}
for (int i = 2; i <= num/i; i++) {
if(num%i == 0){return false;}
}
return true;
}
}
|
闫式C++代码
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
41
42
43
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
int main()
{
int n;
cin >> n;
for (int i = n - 6; i <= n + 6; i += 12)
if (is_prime(i) && is_prime(n))
{
cout << "Yes" << endl;
cout << i << endl;
return 0;
}
for (int i = n + 1;; i ++ )
if (is_prime(i) && (is_prime(i - 6) || is_prime(i + 6)))
{
cout << "No" << endl;
cout << i << endl;
return 0;
}
return 0;
}
作者：yxc
链接：https:
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
