PAT 2019甲级春季考试真题1 Sexy Primes

发布于 / PAT-甲级 / Comments Off on PAT 2019甲级春季考试真题1 Sexy Primes

Sexy primes are pairs of primes of the form (pp+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 (108).

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

题目大意:对于一个数字n,如果n是质数,n+6也是质数,则称他们为孪生质数。

对于给定的数字,判断它是不是孪生质数,如果是,输出另一对。如果不是,找到比这个数大的最小的孪生质数,并输出。

这道题直接模拟即可。

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n){
  if(n < 2) return false;
  if(n == 2) return true;
  for(int i = 2; i <= sqrt(n); i++){
    if(n % i == 0) return false;
  }
  return true;
}

int judge(int num){
  bool isp1 = isPrime(num);
  bool isp2 = isPrime(num - 6);
  bool isp3 = isPrime(num + 6);
  if(isp1 && isp2) return num - 6;
  if(isp1 && isp3) return num + 6;
  return -1;
}

int main(){
  int num;
  cin >> num;
  if(judge(num) != -1){
    cout << "Yes\n" << judge(num) << endl;
    return 0;
  }else{
    do{
      num++;
    }while(judge(num) == -1);
    cout << "No\n" << num << endl;
  }
  return 0;
}

转载原创文章请注明,转载自: 斐斐のBlog » PAT 2019甲级春季考试真题1 Sexy Primes
评论已关闭