POJ NOI0113-05 素数回文数的个数（PKU2928）

问题链接：POJ NOI0113-05 素数回文数的个数。

原题出处：PKU2928 素数回文数的个数。

问题分析

这是一个判定计数的问题，需要判定一个数是否为素数和回文数。

程序说明

函数isprime()用来判定一个数是否是素数；函数ispalindrom()用来判定一个整数是否为回文数，这是一个更为通用的函数，可以指定进制。

使用函数进行判定时，先调用哪个函数也是有讲究的，一要看那个函数的计算时间，二要看判定成功的概率，需要综合考虑。

AC的C++语言程序：

#include <iostream>
#include <cmath>

using namespace std;

const int START = 11;

bool isprime(int n)
{
    if(n == 1)
        return false;

    if(n == 2)
        return true;

    if(n % 2 == 0)
        return false;

    int end = sqrt(n);
    for(long i=3; i<=end; i+=2)
        if(n % i == 0)
            return false;

    return true;
}

bool ispalindrom(int n, int base)
{
    int palindrom = 0, temp;

    temp = n;
    while(temp) {
        palindrom *= base;
        palindrom += temp % base;
        temp /= base;
    }

    return n == palindrom;
}

int main()
{
    int n, count;

    cin >> n;

    count = 0;
    for(int i=START; i<=n; i++)
        if(ispalindrom(i, 10) && isprime(i))
            count++;

    cout << count << endl;

    return 0;
}