PAT甲级-1015. Reversible Primes (20)

清疚 2022-05-30 05:45 153阅读 0赞

# 1015. Reversible Primes (20) #

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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 (< 105) 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

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 1000010
    int a[MAXN];
    long long y=0;
    typedef long long ll;
    bool is_prime[MAXN];
    bool is_prime_small[MAXN];
    void segment_sieve()//素数打表
    {
        for(ll i=0; i*i<=MAXN; ++i)
            is_prime_small[i]=true;
        for(ll i=0; i<=MAXN; ++i)
            is_prime[i]=true;
        is_prime[0]=is_prime[1]=false;//0,1不是素数
        for(ll i=2; i*i<=MAXN; ++i)
        {
            if(is_prime_small[i])
            {
                for(ll j=2*i; j*j<=MAXN; j+=i)
                    is_prime_small[j]=false;
                for(ll j=max(2LL,(i-1)/i)*i; j<=MAXN; j+=i)
                    is_prime[j]=false;
            }
        }
    }
    void changeR(int x,int r)//逆置后转十进制判断是否素数
    {
        y=0;
        int cnt=0;
        while(x>0)
        {
            a[cnt++]=x%r;
            x/=r;
        }
        int temp=1;
        for(int i=cnt-1; i>=0; --i)
        {
            y+=(a[i]*temp);
            temp*=r;
        }
        //cout<<y<<endl;
    }
    int main()
    {
        segment_sieve();
        int x,r;
        while(cin>>x)
        {
            if(x<0) break;
            cin>>r;
            memset(a,0,sizeof(a));
            changeR(x,r);
            if(is_prime[x]&&is_prime[y]) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        return 0;
    }