PAT Advanced 1015. Reversible Pr

题目

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的翻转数是否都是素数

代码

#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;
}