PAT 1156 Sexy Primes

原题链接：PAT 1156 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

题目大意： 按题意进行模拟，感觉是做过的最简单的题了…… 代码：

#include <iostream> using namespace std; const int N = 1e8; bool is_prime(int n){ if(n < 3) return false; for(int i = 2; i * i < n; i ++ ) if(n % i == 0) return false; return true; } int get_sexyprime(int n){ for(int i = n; i < N; i ++ ){ if(is_prime(i) && is_prime(i+6)) return i; else if(is_prime(i) && is_prime(i-6)) return i; } } int main(){ int n; scanf("%d", &n); if(n <= 6){ if(is_prime(n) && is_prime(n+6)){ puts("Yes"); printf("%d", n+6); } else { puts("No"); printf("%d", get_sexyprime(n)); } } if(n > 6){ if(is_prime(n) && is_prime(n-6)){ puts("Yes"); printf("%d", n-6); } else if(is_prime(n) && is_prime(n+6)){ puts("Yes"); printf("%d", n+6); } else { puts("No"); printf("%d", get_sexyprime(n)); } } return 0; }