A1015 Reversible Primes (20分)

/*
题意：
1、给出一个数字，以及一个进制
2、判断一个数以及他的相反数是素数吗，是则输出
3、输入一个负数代表结束

解题：
1、需要一个反转函数，一个转换进制函数
2、素数表，以及散列表速度查询

learn && worng:
1、while的这个输入条件我忘了
2、除基取余第一个是低位别忘了
3、题意错，逻辑复杂，不如答案简单——直接取余，然后成绩取整，从0开始，因为0是低位
4、判断素数，记得是从2开始，余上0会报错，余上1，永远都不是素数
5、10的5次方，转为二进制，不会超过2的32，所以数组不用开那么大

*/

#include <iostream>
#include <cmath>
using namespace std;

const int maxn = 10000; //!!!maxn也没有很大

//素数表
int prime[maxn], num_prime = 0;
bool p[maxn] = { 0 };

bool isprime(int n) {
    if (n <= 1) return false;
    int sqr = (int)sqrt(1.0 * n);
    for (int i = 2;i <= sqr;++i) {  //！！！这里错了，不是从0开始的！
        if (n % i == 0)
            return false;
    }
    return true;
}

//除基取余
int bianhuan(int n, int D) {
    int num = 0;
    int array_quyu[maxn];
    do {    //变换进制没错
        array_quyu[num++] = n % D;
        n /= D;
    } while (n != 0);

    int temp = 0;
    for (int i = 0;i < num;++i) {   //!!!逆序转换十进制
        temp = temp * D + array_quyu[i];
    }
    return temp;
}




int main(int argc, char** argv) {
    int N, D;
    while (scanf("%d%d", &N, &D), N > 0) {
        if (isprime(N) == false) {
            cout << "No" << endl;
        }
        else {
            int num1 = bianhuan(N, D);
            if (isprime(num1) == true) {
                cout << "Yes" << endl;
            }
            else {
                cout << "No" << endl;
            }
        }

    }

    return 0;
}