PAT（甲级）2019年春季考试7-1 Sexy Primes (20 分)

本文主要是介绍PAT（甲级）2019年春季考试7-1 Sexy Primes (20 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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:

Sample Output 1:

Yes
41

Sample Input 2:

Sample Output 2:

No
23

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n) {if (n <= 1) return false;int sqr = sqrt(1.0 * n);for (int i = 2; i <= sqr; i++) {if (n % i == 0) return false;}return true;
}
int main() {int N;scanf("%d", &N);if (isPrime(N)) {if (isPrime(N - 6)) {printf("Yes\n%d", N - 6);return 0;}if (isPrime(N + 6)) {printf("Yes\n%d", N + 6);return 0;}}printf("No\n");if (N % 2 == 0) N++;for (int i = N + 2; ; i += 2) {if (isPrime(i) && (isPrime(i - 6) || isPrime(i + 6))) {printf("%d", i);return 0;}}return 0;
}