1015. Reversible Primes (20)

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 N (< 10⁵) and D (1 < D <= 10), you are supposed to tell if N is a reversible prime with radix D.

Input Specification:

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

Output Specification:

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

Sample Input:

73 10 23 2 23 10 -2

Sample Output:

Yes Yes No

采用素数筛选法，若$i$为素数，则$i*j$不是素数，其中$j=2,3,....$。这样可以不用判断哪个数为素数，因为非素数的都必定会被筛选出来。

 

代码

#include <stdio.h>

#include <math.h>

char primerTable[500000];

void calculatePrimerTable();

int num2array(int,int,int*);

int array2num(int*,int,int);

int main()

{

    calculatePrimerTable();

    int N,D,len;

    int data[32];

    while(scanf("%d",&N)){

        if(N < 0)

            break;

        scanf("%d",&D);

        if(primerTable[N] == 'N'){

            printf("No\n");

            continue;

        }

        len = num2array(N,D,data);

        if(primerTable[array2num(data,len,D)] == 'Y')

            printf("Yes\n");

        else

            printf("No\n");

    }

    return 0;

}

void calculatePrimerTable()

{

    int i;

    for(i=2;i<500000;i++){

        if(primerTable[i] != 'N'){

            primerTable[i] = 'Y';

            int j,n;

            for(j=2,n=2*i;n<500000;++j,n=j*i){

                primerTable[n] = 'N';

            }          

        }

    }

}

int num2array(int n,int base,int *s)

{

    if(n < 0)

        return 0;

    else if(n == 0){

        s[0] = 0;

        return 1;

    }

    int len = 0;

    while(n){

        s[len++] = n % base;

        n = n / base;

    }

    return len;

}

int array2num(int *s,int len,int base)

{

    int i,n = 0;

    for(i=0;i<len;++i){

        n = n * base + s[i];

    }

    return n;

}