A1156 SexyPrimes (20 points)

素数判断

1. 原文

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

2. 解析思路

判断n以及n-6或者n+6是素数，不是的话，那就n++，直到满足要求

3. AC代码

#include<cstdio>
#include<cmath>
bool isPrime(int x){
	if (x<2)
	{
		return false;
	}
	int sqr = sqrt(1.0*x);
	for (int i = 2; i <= sqr; ++i)
	{
		if (x%i==0)
		{
			return false;
		}
	}
	return true;
}
int judge(int x){
	if (isPrime(x))
	{
		bool f1 = isPrime(x-6);
		bool f2 = isPrime(x+6);
		if (f1||f2)
		{
			return f1?(x-6):(x+6);
		}
	}
	return -1;
}
int main(){
	int n;
	scanf("%d",&n);
	int ans = judge(n);
	if (ans>0)
	{
		printf("Yes\n%d\n",ans);
	}else{
		while(judge(n)<0){
			n++;
		}
		printf("No\n%d\n",n);
	}

	return 0;
}