PAT(甲级)2019年春季考试 7-1 Sexy Primes
文章目录
7-1 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:
47Sample Output 1:
Yes
41Sample Input 2:
21Sample Output 2:
No
23题目限制
| 时间限制 | 内存限制 |
|---|---|
| 400 ms | 64 MB |

题目大意:
一个数x是“sexy prime”指的是x是质数且x-6或x+6也是质数。给出一个数,判断这个数是不是“sexy prime”,如果是的话输出与这个数配对的另一个“sexy prime”,如果有多个就输出小的那个(也就是x-6),如果不是就输出最小的比这个数大的“sexy prime”。
算法思路:
使用isPrime函数判断一个数N是否为素数,然后对于输入的数字N,首先判断N和N-6是否为素数,如果是,输出Yes和N-6,否则判断N和N+6是否为素数,如果是,输出Yes和N+6,如果都不是,说明N不是sexy prime,输出No,然后从N+1开始遍历每一个数字i,判断i和i-6是否为素数,如果是输出i并结束程序,否则判断i和i+6是否为素数,如果是输出i并结束程序。
isPrime函数
bool isPrime(int N){
if(N<=1) return false;
int sqrtn = (int)sqrt(N*1.0);
for (int i = 2; i <= sqrtn; ++i) {
if(N%i==0) return false;
}
return true;
}提交结果:

AC代码:
#include<cstdio>
#include <cmath>
using namespace std;
bool isPrime(int N){
if(N<=1) return false;
int sqrtn = (int)sqrt(N*1.0);
for (int i = 2; i <= sqrtn; ++i) {
if(N%i==0) return false;
}
return true;
}
int main(){
int N;
scanf("%d",&N);
if(isPrime(N)&&isPrime(N-6)){
// N是sexy prime,找到仅次于N的sexy prime
printf("Yes\n%d",N-6);
} else if(isPrime(N)&&isPrime(N+6)){
printf("Yes\n%d",N+6);
} else {
// N不是sexy prime,找到仅大于N的sexy prime
printf("No\n");
for (int i = N+1; ; ++i) {
if(isPrime(i)&&isPrime(i-6)){
printf("%d",i);
break;
}
if(isPrime(i)&&isPrime(i+6)){
printf("%d",i);
break;
}
}
}
return 0;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论