【华为OD机试真题】【2024年E卷】生成回文素数-模拟(C++/Java/Python)

分值：100

题目描述

求出大于或等于 N 的最小回文素数Q。
回顾一下，如果一个数大于 1，且其因数只有1和它自身，那么这个数是素数。
例如，2,3,5,7,11以及 13 是素数。
回顾一下，如果一个数从左往石读与从右往左读是一样的，那么这个数是回文数Q例如，12321 是回文数。
输入描述:
一个数字 N。
输出描述:
一个大于或等于 N 的最小回文素数Q。

示例1
输入：
6
输出：
7
解释： 大于或等于 6 的最小回文素数7。

示例2
输入：
8
输出：
11

Tips:

• 1 <= N <= 1e8
• 测试用例保证答案总是存在，并且在 [2, 2 * 108] 范围内

思路

• “偶数长度的回文数”中只有11是素数，其他的都可以被11整除。所以可以直接跳过偶数长度的回文数（除了 11）。
• 跳过 1e7 ~ 1e8 这段数字远比跳过1e5~1e6…这些加起来多得多，复杂度优化主要集中在跳过1e7 ~ 1e8这段。当然，也可以特判其他长度的数字进行跳过，只是影响不大。
• 思路参考自866. 回文质数力扣官方题解

复杂度分析

• 时间复杂度： $O(N)$，其中N为数字大小
• 空间复杂度： $O(1)$

AC 代码

C++ 版

#include <bits/stdc++.h>
using namespace std;
int primePalindrome(int N) {
    while (true) {
        if (N == reverse(N) && isPrime(N)) {
            return N;
        }
        N++;
        // 知识点： “偶数长度的回文数”中只有11是素数，其他的都可以被11整除。所以可以直接跳过偶数长度的回文数（除了 11）。
        // 
        if (1e7 < N && N < 1e8) {
            N = 1e8;
        }
    }
}

bool isPrime(int N) {
    if (N < 2) return false;
    int R = static_cast<int>(sqrt(N));
    for (int d = 2; d <= R; ++d)
        if (N % d == 0) return false;
    return true;
}

int reverse(int N) {
    int ans = 0;
    while (N > 0) {
        ans = 10 * ans + (N % 10);
        N /= 10;
    }
    return ans;
}
int main()
{
    int n;
    cin >> n;
    cout << primePalindrome(n);
    return 0;
}

JAVA 版

import java.util.Scanner;

public class PrimePalindrome {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(primePalindrome(n));
        scanner.close();
    }

    public static int primePalindrome(int N) {
        while (true) {
            if (N == reverse(N) && isPrime(N)) {
                return N;
            }
            N++;
            if (1e7 < N && N < 1e8) {
                N = (int) 1e8;
            }
        }
    }

    public static boolean isPrime(int N) {
        if (N < 2) return false;
        int R = (int) Math.sqrt(N);
        for (int d = 2; d <= R; ++d)
            if (N % d == 0) return false;
        return true;
    }

    public static int reverse(int N) {
        int ans = 0;
        while (N > 0) {
            ans = 10 * ans + (N % 10);
            N /= 10;
        }
        return ans;
    }
}

Python 版

import math

def primePalindrome(N):
    def isPrime(num):
        if num < 2:
            return False
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

    def reverse(num):
        reversed_num = 0
        while num > 0:
            reversed_num = reversed_num * 10 + num % 10
            num //= 10
        return reversed_num

    while True:
        if N == reverse(N) and isPrime(N):
            return N
        N += 1
        if 1e7 < N < 1e8:
            N = int(1e8)

n = int(input())
print(primePalindrome(n))