P1217 回文质数题解

· · 题解

洛谷 P1217 回文质数题解

通过循环递推的方法先生成所有回文数，再判断是否为素数。

思路分析

首先分为奇数位回文数和偶数位回文数，两者思路一致，以奇数位回文数为例。

所有 3 位回文数的模式为 aba，其中 a 为 1 到 9 的数字，b 为 0 到 9 的数字；5 位回文数的模式为 abcba，其中 a 为 1 到 9 的数字，b 和 c 为 0 到 9 的数字。可以看出 5 位回文数的中间 3 位必然也是回文数，且是三位回文数的超集，因为前后数字可以为 0。因此中间 3 位前后为 1 到 9 的 5 位回文数，可以由所有 3 位回文数在前后加上 1 到 9 的数字得到；而中间 3 位前后为 0 的 5 位回文数，可以由前后为 1 的 3 位回文数生成的 5 位回文数，减去前后为 1 的最小的 3 位回文数 \times 10 得到，如 10001 = 11011 - 101 \times 10, 10101 = 11111 - 101 \times 10，以此类推。

代码实现思路

  1. 一个数组按序存储已有的 n（n 为奇数或偶数）位回文数，另一个新的数组按序存储要生成的 n+2 位回文数。
  2. 两层 for 循环，第一层遍历 1 到 9，即前后要加的数字；第二层有两个 for 循环，第一个 for 循环是为了生成中间部分前后为 0 的 n+2 位回文数，通过遍历 n 位回文数中前后为 1 的所有回文数（即数组的前 \frac{1}{9} 个数）并生成 n+2 位回文数后（生成方式比较简单，详见代码），减去数组中第 1 个元素（前后为 1 且最小）乘 10 得到。第二个 for 循环是为了生成中间部分前后为 1 到 9 的 n+2 位回文数，通过遍历所有 n 位回文数并生成 n+2 位回文数得到。两个 for 循环生成的 n+2 位回文数依次填入新数组即可。

其它的实现细节详见代码。

C语言完整代码


# include <stdio.h>
# include <math.h>
# include <string.h>

// 计算数字位数
int countDigits(const int n) {
    return (int) log10(n) + 1;
}

// 判断是否为素数
int isPrime(const int n) {
    int isPrime = 1;
    if (n <= 1) {
        isPrime = 0;
    }
    for (int i = 2; i * i <= n; i++) { // 小优化，不用sqrt浮点运算
        if (n % i == 0) {
            isPrime = 0;
            break; // 及时跳出可以节约很多时间
        }
    }
    return isPrime;
}

// 根据上一个位数的回文数生成新的回文数
int createNextDigitsPalindromes(int lastDigitsPalindromes[], const int lastLen, int nextDigitsPalindromes[]) {
    int lastDigits = countDigits(lastDigitsPalindromes[0]); // 上一个回文数的位数
    int palindrome; // 临时变量
    int len = 0; // 新数组的长度计数变量
    for (int i = 1; i < 10; i++) {
        for (int j = 0; j < lastLen / 9; j++) {
            palindrome = lastDigitsPalindromes[j] * 10 + i * pow(10, lastDigits + 1) + i;
            palindrome -= lastDigitsPalindromes[0] * 10;
            nextDigitsPalindromes[len++] = palindrome;
        }
        for (int j = 0; j < lastLen; j++) {
            palindrome = lastDigitsPalindromes[j] * 10 + i * pow(10, lastDigits + 1) + i;
            nextDigitsPalindromes[len++] = palindrome;
        }
    }
    return len;
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int oddPalindromes[10000] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 奇数位回文数
    int evenPalindromes[10000] = {11, 22, 33, 44, 55, 66, 77, 88, 99}; // 偶数位回文数
    int palindromes[10000]; // 新生成的回文数
    int lastLen = 9, newLen; // 上一个位数的回文数的个数和新生成的回文数的个数
    int *p; // 临时变量
    int palindrome; // 临时变量

    // 特判
    for (int i = 0; i < lastLen; i++) {
        palindrome = oddPalindromes[i];
        if (palindrome >= a && palindrome <= b && isPrime(palindrome)) {
            printf("%d\n", palindrome);
        }
    }
    for (int i = 0; i < lastLen; i++) {
        palindrome = evenPalindromes[i];
        if (palindrome >= a && palindrome <= b && isPrime(palindrome)) {
            printf("%d\n", palindrome);
        }
    }

    // 缩小边界，节约时间和空间
    if (b == 1e8) {
        b -=1;
    }

    // 奇/偶数位回文数交替生成，直到b的位数为止
    for (int i = 0; i < countDigits(b) - 2; i++) {
        p = i % 2 == 0 ? oddPalindromes : evenPalindromes;
        newLen = createNextDigitsPalindromes(p, lastLen, palindromes);
        for (int j = 0; j < newLen; j++) {
            palindrome = palindromes[j];
            if (palindrome >= a && palindrome <= b && isPrime(palindrome)) {
                printf("%d\n", palindrome);
            }
        }
        memcpy(p, palindromes, newLen * sizeof(int)); // 更新数组
        if (i % 2 == 1) {
            lastLen = newLen; // 奇/偶数位回文数的个数相同，统一更新
        }
    }

    return 0;
}