A1156 Sexy Primes (20 分)

A1156 Sexy Primes (20 分)

Problem：

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也为素数， 我们称这样的一对素数(P, P + 6) 为 sexy primes ，则P就为sexy prime

题目给你一个整数N，让后然你判断是否为sexy prime，

1. 如果N是，则第一行输出Yes，第二行输出另一个sexy prime，如果答案不唯一则输出比较小的那个sexy prime ；
2. 如果N不是，则第一行输出No，第二行输出大于N的最小sexy prime

思路

1. 写一个判断是否是素数的函数，isPrime(int x)

2. 然后分别判断N - 6 和 N + 6是否是素数

   • 如果是，则输出N - 6
   • 如果N - 6不是素数，N + 6是素数，则输出N + 6。

3. 如果N - 6 和 N + 6都不是素数，则N不是sexy prime,

   • 对N自增，直到(isPrime(N) && (isPrime(N + 6) || isPrime(N - 6))) == true
   • 这里特别要注意不仅仅要判断 N + 6是否是素数，也要判断N - 6是否是素数，这里对N - 6的判断容易写漏
   • （PS: 我开始时这里就写漏了，导致好久都没通过测试点3）

AC代码

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x) {
    if (x <= 1) {
        return false;
    }
    int n = sqrt(x * 1.0);
    for (int i = 2; i <= n; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int N;
    int res = 0;
    scanf("%d", &N);
    bool b1 = isPrime(N - 6);
    bool b2 = isPrime(N + 6);
    if (isPrime(N) && (b1 || b2)) {
        if (b1) {
            res =  N - 6;
        } else {
            res = N + 6;
        }
        printf("Yes\n%d", res);
    } else {
        while (1) {
            if (isPrime(N) && (isPrime(N + 6) || isPrime(N - 6))) {
                break;
            }
            ++N;
        }
        printf("No\n%d\n", N);
    }
    return 0;
}