PAT甲级【2019年3月考题】——A1156 SexyPrimes【20】

Sexy primes are pairs of primes of the form (p, p+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)

Now given an integer, you are supposed to tell if it is a sexy prime.

Input Specification:
Each input file contains one test case. Each case gives a positive integer N (≤108 10^810
8
).

Output Specification:
For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.

Sample Input 1:
47
Sample Output 1:
Yes
41
Sample Input 2:
21
Sample Output 2:
No
23

【声明】

　　由于此题还未上PAT官网题库，故没有测试集，仅仅是通过了样例，若发现错误，感谢留言指正。

Solution：

　　这道题很简单，就是判断一下n 以及 n-6 或者 n+6是素数，不是的话，那就n++，直到满足要求

 1 #include <iostream>
 2 using namespace std;
 3 bool isPrime(int x)//判断是不是素数
 4 {
 5     if (x < 3)
 6         return x >= 1;
 7     for (int i = 2; i*i <= x; ++i)
 8         if (x%i == 0)
 9             return false;
10     return true;
11 }
12 int isSexyPrimes(int x)//判断满不满足题目要求
13 {
14     if (isPrime(x))
15     {
16         bool fL = isPrime(x - 6), fR = isPrime(x + 6);
17         if (fL || fR)
18             return fL ? x - 6 : x + 6;
19     }
20     return -1;
21 }
22 int main()
23 {
24     int n;
25     cin >> n;
26     int res = isSexyPrimes(n);
27     if (res > 0)
28     {
29         printf("Yes
");
30         printf("%d
", res);
31     }
32     else
33     {
34         printf("No
");
35         for (int i = n + 1; i < INT32_MAX; ++i)//另寻找大数，直至满足要求
36         {
37             if (isSexyPrimes(i) > 0)
38             {
39                 printf("%d
", i);
40                 break;
41             }
42         }
43     }
44     return 0;
45 }