PAT Advanced 1015. Reversible Pr

我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。

题目

A reversible prime in any number system is a prime whose "reverse" in that
number system is also a prime. For example in the decimal system 73 is a
reversible prime because its reverse 37 is also a prime.

Now given any two positive integers ( ) and (
), you are supposed to tell if is a reversible prime with radix .

Input Specification:

The input file consists of several test cases. Each case occupies a line which
contains two integers and . The input is finished by a negative .

Output Specification:

For each test case, print in one line Yes if is a reversible prime with
radix , or No if not.

Sample Input:

73 10
23 2
23 10
-2

Sample Output:

Yes
Yes
No

思路

思路很简单：

• 求得"翻转数"。应该比较简单，具体实现见下面Rev函数
• 判断N和N的翻转数是否都是素数

判断输入终止的方法：利用scanf的返回值。scanf的返回值为scanf已转化的
格式化标识符的个数，因此最后只有一个负数标识结束的时候，scanf会返回1，其余时候
返回2，因此用的代码中的while(scanf(...))的形式，非常简洁。

代码

最新代码@github，欢迎交流

#include <stdio.h>

int iPrime(int N)
{
    if(N == 0 || N == 1)
        return 0;
    for(int i = 2; i * i <= N; i++)
        if(N % i == 0)
            return 0;
    return 1;
}

int Rev(int N, int D)
{
    int Nrev;
    for(Nrev = 0; N; N /= D)
    {
        Nrev *= D;
        Nrev += N % D;
    }
    return Nrev;
}

int main()
{
    int N, D;

    while(scanf("%d %d", &N, &D) == 2)
        puts(iPrime(N) && iPrime(Rev(N, D)) ? "Yes" : "No");

    return 0;
}