PAT A1156 Sexy Primes (20point(s))

Scroll Down

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

解答

#include<iostream>
#include<cmath>

using namespace std;

bool isPrime(int n) {
	if (n < 2) return false; // 坑点2
	if (n == 2 || n == 3) return true;
	int sqrtn = (int)sqrt(n);
	if (n % 6 != 5 && n % 6 != 1) 
		return false;
	for (int i = 5; i <= sqrtn; i+=6) 
		if (n%i == 0 || n % (i + 2) == 0) 
			return false;
	return true;
}
int main()
{
	int n, ans = -1;
	scanf("%d", &n);
	if (isPrime(n - 6) && isPrime(n)) ans = n - 6;
	else if (isPrime(n + 6) && isPrime(n)) ans = n + 6;
	else 
		while ((!isPrime(n) || !isPrime(n + 6)) && (!isPrime(n) || !isPrime(n - 6))) n++;// 坑点1
	if (ans == -1) printf("No\n%d", n);
	else printf("Yes\n%d", ans);
	return 0;
}