1156 Sexy Primes – PAT甲级真题

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).

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

题目大意：性感素数是指形如 (p, p+6) 这样的一对素数。给定一个整数，判断其是否为一个性感素数。若N是一个性感素数，则在一行中输出Yes，并在第二行输出与N配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。若N不是性感素数，则在一行中输出No，然后在第二行输出大于N的最小性感素数。

分析：is_prime判断是否为素数。判断p和p-6、p和p+6是否同时为素数，如果是，则为性感素数输出Yes。不是的话就从p+1往后找到第一个满足要求的数ans~ 

#include 
#include 
using namespace std;
int p, ans;
int is_prime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return 0; 
    return 1;
}
int main() {
    cin >> p;
    if (is_prime(p) && is_prime(p - 6)) {
        cout << "Yes\n" << p - 6;
    } else if (is_prime(p) && is_prime(p + 6)) {
        cout << "Yes\n" << p + 6;
    } else {
        for (ans = p + 1; ; ans++) {
            if (is_prime(ans) && is_prime(ans - 6)) break;
            if (is_prime(ans) && is_prime(ans + 6)) break;
        }
        cout << "No\n" << ans;
    }
    return 0;
}