关于算法-数据结构:PAT甲级2019年春季考试-71-Sexy-Primes

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:

Yes
41

Sample Input 2:

21

Sample Output 2:

No
23

题目限度

题目粗心：

一个数 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;
}