PAT Basic 1099. 性感素数

1. 题目描述：

“性感素数”是指形如 \((p, p+6)\) 这样的一对素数。之所以叫这个名字，是因为拉丁语管“六”叫“sex”（即英语的“性感”）。（原文摘自 http://mathworld.wolfram.com/SexyPrimes.html）

现给定一个整数，请你判断其是否为一个性感素数。

2. 输入格式：

输入在一行中给出一个正整数 \(N\) (\(≤10^8\))。

3. 输出格式：

若 \(N\) 是一个性感素数，则在一行中输出 Yes，并在第二行输出与 \(N\) 配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。若 \(N\) 不是性感素数，则在一行中输出 No，然后在第二行输出大于 \(N\) 的最小性感素数。

4. 输入样例：

47

21

5. 输出样例：

Yes
41

No
23

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

此题会判断素数即可，但难点是逻辑处理容易漏掉一些条件，这可能也是此题通过率较低的原因。。。第一次提交时testpoint2，3报wrong answer，以为是当\(N\)不是素数时，找大于\(N\)的最小素数超出了int类型上限，就把int类型都改为long类型，但testpoint2，3依旧报错。。。于是检查逻辑处理部分，这里主要涉及以下坑点：

• 在对num-6和num+6进行判断时，遗漏了对num本身的判断，加上后过了testpoint2
• 当num本身不是素数时，递增num的条件判断中遗漏了对num-6的判断，加上后过了testpoint3

另外要注意在素数判断函数isPrime()中对0和1的处理，两个都不是素数。最后将long类型改回int类型发现也可以AC，不会超出int类型上限。

My Code:

#include <stdio.h>

// int isPrime(int num);
int isPrime(long num);

// first submit testpoint2, 3 wrong answer
// after rectify from int to long, testpoint2, 3 still wrong answer
int main(void)
{
    // int num=0;
    long num=0;
    
    scanf("%ld", &num);
    
    if(isPrime(num-6) && isPrime(num)) // forget to judge num itself, this fixed testpoint2
    {
        printf("Yes\n%ld\n", num-6);
    }
    else if(isPrime(num+6) && isPrime(num))
    {
        printf("Yes\n%ld\n", num+6);
    }
    else // num is not a sex Prime
    {
        ++num;
        while(!isPrime(num) || (!isPrime(num+6) && !isPrime(num-6))) //while(!isPrime(num) || !isPrime(num+6)) this add judge isPrime(num-6), fixed testpoint3
        {
            ++num;
        }
        printf("No\n%ld\n", num);
    }
    
    
    return 0;
}

int isPrime(long num)
{
    if(num<=1) return 0; // 0 and 1 is not a prime
    
    for(long i=2; i*i<=num; ++i)
    {
        if(num % i == 0)
        {
            return 0; // not a prime
        }
    }
    return 1;
}


// #include <stdio.h>

// // int isPrime(int num);
// int isPrime(int num);

// // first submit testpoint2, 3 wrong answer
// // after rectify from int to long, testpoint2, 3 still wrong answer
// int main(void)
// {
//     // int num=0;
//     int num=0;
    
//     scanf("%d", &num);
    
//     if(isPrime(num-6) && isPrime(num)) // forget to judge num itself, this fixed testpoint2
//     {
//         printf("Yes\n%d\n", num-6);
//     }
//     else if(isPrime(num+6) && isPrime(num))
//     {
//         printf("Yes\n%d\n", num+6);
//     }
//     else // num is not a sex Prime
//     {
//         ++num;
//         while(!isPrime(num) || (!isPrime(num+6) && !isPrime(num-6))) //while(!isPrime(num) || !isPrime(num+6))
//         {
//             ++num;
//         }
//         printf("No\n%d\n", num);
//     }
    
    
//     return 0;
// }

// int isPrime(int num)
// {
//     if(num<=1) return 0; // 0 and 1 is not a prime
    
//     for(int i=2; i*i<=num; ++i)
//     {
//         if(num % i == 0)
//         {
//             return 0; // not a prime
//         }
//     }
//     return 1;
// }