【华为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                         )                              O(N)                  O(N)，此中N为数字巨细
  
• 空间复杂度：                                    O                         (                         1                         )                              O(1)                  O(1)
  

AC 代码

C++ 版

1. #include <bits/stdc++.h>
2. using namespace std;
3. int primePalindrome(int N) {
4.     while (true) {
5.         if (N == reverse(N) && isPrime(N)) {
6.             return N;
7.         }
8.         N++;
9.         // 知识点： “偶数长度的回文数”中只有11是素数，其他的都可以被11整除。所以可以直接跳过偶数长度的回文数（除了 11）。
10.         //
11.         if (1e7 < N && N < 1e8) {
12.             N = 1e8;
13.         }
14.     }
15. }
17. bool isPrime(int N) {
18.     if (N < 2) return false;
19.     int R = static_cast<int>(sqrt(N));
20.     for (int d = 2; d <= R; ++d)
21.         if (N % d == 0) return false;
22.     return true;
23. }
25. int reverse(int N) {
26.     int ans = 0;
27.     while (N > 0) {
28.         ans = 10 * ans + (N % 10);
29.         N /= 10;
30.     }
31.     return ans;
32. }
33. int main()
34. {
35.     int n;
36.     cin >> n;
37.     cout << primePalindrome(n);
38.     return 0;
39. }

复制代码

JAVA 版

1. import java.util.Scanner;
3. public class PrimePalindrome {
5.     public static void main(String[] args) {
6.         Scanner scanner = new Scanner(System.in);
7.         int n = scanner.nextInt();
8.         System.out.println(primePalindrome(n));
9.         scanner.close();
10.     }
12.     public static int primePalindrome(int N) {
13.         while (true) {
14.             if (N == reverse(N) && isPrime(N)) {
15.                 return N;
16.             }
17.             N++;
18.             if (1e7 < N && N < 1e8) {
19.                 N = (int) 1e8;
20.             }
21.         }
22.     }
24.     public static boolean isPrime(int N) {
25.         if (N < 2) return false;
26.         int R = (int) Math.sqrt(N);
27.         for (int d = 2; d <= R; ++d)
28.             if (N % d == 0) return false;
29.         return true;
30.     }
32.     public static int reverse(int N) {
33.         int ans = 0;
34.         while (N > 0) {
35.             ans = 10 * ans + (N % 10);
36.             N /= 10;
37.         }
38.         return ans;
39.     }
40. }

复制代码

Python 版

1. import math
3. def primePalindrome(N):
4.     def isPrime(num):
5.         if num < 2:
6.             return False
7.         for i in range(2, int(math.sqrt(num)) + 1):
8.             if num % i == 0:
9.                 return False
10.         return True
12.     def reverse(num):
13.         reversed_num = 0
14.         while num > 0:
15.             reversed_num = reversed_num * 10 + num % 10
16.             num //= 10
17.         return reversed_num
19.     while True:
20.         if N == reverse(N) and isPrime(N):
21.             return N
22.         N += 1
23.         if 1e7 < N < 1e8:
24.             N = int(1e8)
26. n = int(input())
27. print(primePalindrome(n))

复制代码