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

我会带着你远行 2023-02-20 15:57 13阅读 0赞

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][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:

Sample Output 1:

Yes
    41

Sample Input 2:

Sample Output 2:

No
    23

## 题意 ##

一个数x是“sexy prime”指的是x是质数且x-6或x+6也是质数。  
给出一个数，判断这个数是不是“sexy prime”，如果是的话输出与这个数配对的另一个“sexy prime”，如果有多个就输出小的那个（也就是x-6），如果不是就输出最小的比这个数大的“sexy prime”。  
代码

# 标题 #

题目未开放，代码没有在官网测试。

//if顺序 int范围 if()判断 
    #include <bits/stdc++.h>
    using namespace std;
    bool isPrime(int n){ 
    	if(n<=1)return false;
    	int sqr= (int)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-6)){ 
    		printf("Yes\n");
    		printf("%d",n-6);
    	}else if(isPrime(n+6)){ 
    		printf("Yes\n");
    		printf("%d",n+6);
    	}else{ 
    		for(int i=n+1;i<=100000000;i++){ 
    			if(isPrime(i-6)+isPrime(i+6)){ 
    				printf("No\n");
    				printf("%d",i);
    				break;
    			}	
    		}
    	}
    	return 0;
    }

[http_mathworld.wolfram.com_SexyPrimes.html]: http://mathworld.wolfram.com/SexyPrimes.html