1015_Reversible_Primes（20）

Describe

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
No

代码长度限制                        16 KB

时间限制                                400 ms

内存限制                                64 MB

Code：

刚开始题目都没有看懂，总是不能理解radix是什么意思，做题目做少了（下次看到radix就想到可能需要进制的转换）我很想知道我总是最后一个测试点过不去，刚开始只得到了16分，是因为判断素数的时候没有把1考虑进去，加上之后还是只有18分😭，希望在评论区有大佬可以帮我找到错误。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<set>
using namespace std;
bool isPrime(int n){
    if(n<=1) return false;
    for(int i=2; i*i<=n; i++){//要加上=号
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    //加入自己的代码
    long long n ,d;
    while(cin>>n>>d){
        int arr[50], index=0;
        int flag = 0;
        if(n<0)
            return 0;
        if(isPrime(n))
            flag=1;
        do{
            arr[index++] = n%d;
            n=n/d;
        }while(n!=0);
        for(int i=0; i<index; i++){
            n=n*d+arr[i];
        }
        if(isPrime(n))
            flag=2;
        if(flag==2){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

在这里贴上柳神的代码，思路基本一样的。

#include <cstdio>
#include <cmath>
using namespace std;
bool isprime(int n) {
    if(n <= 1) return false;
    int sqr = int(sqrt(n * 1.0));
    for(int i = 2; i <= sqr; i++) {
        if(n % i == 0)
            return false;
    }
    return true;
}
int main() {
    int n, d;
    while(scanf("%d", &n) != EOF) {
        if(n < 0) break;
        scanf("%d", &d);
        if(isprime(n) == false) {
            printf("No\n");
            continue;
        }
        int len = 0, arr[100];
        do{
            arr[len++] = n % d;
            n = n / d;
        }while(n != 0);
        for(int i = 0; i < len; i++)
            n = n * d + arr[i];
        printf("%s", isprime(n) ? "Yes\n" : "No\n");
    }
    return 0;
}