7-1 Sexy Primes (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 (≤10^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:

Yes41

Sample Input 2:

21

Sample Output 2:

No23

题目限度

工夫限度内存限度
400 ms64 MB

题目粗心：

一个数x是“sexy prime”指的是x是质数且x-6或x+6也是质数。给出一个数，判断这个数是不是“sexy prime”，如果是的话输入与这个数配对的另一个“sexy prime”，如果有多个就输入小的那个（也就是x-6），如果不是就输入最小的比这个数大的“sexy prime”。

算法思路：

应用isPrime函数判断一个数N是否为素数,而后对于输出的数字N，首先判断N和N-6是否为素数，如果是，输入Yes和N-6，否则判断N和N+6是否为素数，如果是，输入Yes和N+6，如果都不是，阐明N不是sexy prime,输入No,而后从N+1开始遍历每一个数字i，判断i和i-6是否为素数，如果是输入i并完结程序，否则判断i和i+6是否为素数，如果是输入i并完结程序。

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

提交后果：

AC代码：

#include<cstdio>#include <cmath>using namespace std;bool isPrime(int N){    if(N<=1) return false;    int sqrtn = (int)sqrt(N*1.0);    for (int i = 2; i <= sqrtn; ++i) {        if(N%i==0) return false;    }    return true;}int main(){    int N;    scanf("%d",&N);    if(isPrime(N)&&isPrime(N-6)){        // N是sexy prime,找到仅次于N的sexy prime        printf("Yes\n%d",N-6);    } else if(isPrime(N)&&isPrime(N+6)){        printf("Yes\n%d",N+6);    } else {        // N不是sexy prime,找到仅大于N的sexy prime        printf("No\n");        for (int i = N+1; ; ++i) {            if(isPrime(i)&&isPrime(i-6)){                printf("%d",i);                break;            }            if(isPrime(i)&&isPrime(i+6)){                printf("%d",i);                break;            }        }    }    return 0;}