本文涉及知识点

数论：质数、最大公约数、菲蜀定理

LeetCode 866. 回文质数

给你一个整数 n ，返回大于或等于 n 的最小 回文质数。
一个整数如果恰好有两个除数：1 和它本身，那么它是 质数 。注意，1 不是质数。
例如，2、3、5、7、11 和 13 都是质数。
一个整数如果从左向右读和从右向左读是相同的，那么它是 回文数 。
例如，101 和 12321 都是回文数。
测试用例保证答案总是存在，并且在 [2, 2 * 10⁸] 范围内。
示例 1：
输入：n = 6
输出：7
示例 2：
输入：n = 8
输出：11
示例 3：
输入：n = 13
输出：101
提示：
1 <= n <= 10⁸

质数判断

从小到大判断m位数是否 回文质数，且大于等于n。如果是，则直接返回。本题一定有解。
for i = 1 To 10^m/2-1
str1 = to_string(i)
如果m是奇数，则str1+转置(str1)
如果m是欧式，for(int j = 0;j < 10;j++ ) str1 +(‘0’+j) + 转置(str1)

预处理

预处理[2,2$\times$10⁸]的所有回文质数，并排序。
总数量cnt 不超过2 $\times$ 10⁴ ，时间复杂度：O(cnt logcnt)。

代码

核心代码

class Solution {
		public:
			int primePalindrome(int n) {
				static vector<int> v = Init();
				auto it = lower_bound(v.begin(), v.end(), n);
				return *it;
			}
			bool IsPrime(int n) {
				for (int i = 2; i * i <= n; i++) {
					if (0 == n % i) { return false; }
				}
				return true;
			}
			vector<int> Init() {
				vector<int> ret = { 2,3,5,7 };
				auto Add = [&](int n) {
					if (IsPrime(n))ret.emplace_back(n);
				};
				for (int unit = 10; unit <= 10000; unit *= 10)
				{
					for (int j = unit/10; j < unit; j++) {
						string str1 = to_string(j);
						string str2(str1.rbegin(), str1.rend());
						const int j2 = atoi(str2.c_str());
						Add(j * unit + j2);
						for (int k = 0; k < 10; k++) {
							Add((j * 10 + k) * unit + j2);
						}
					}
				}
				sort(ret.begin(), ret.end());
				return ret;
			}
		};

单元测试

TEST_METHOD(TestMethod1)
		{
			auto res = Solution().primePalindrome(1);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod11)
		{			
			auto res = Solution().primePalindrome(6);
			AssertEx(7, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().primePalindrome(8);
			AssertEx(11, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().primePalindrome(13);
			AssertEx(101, res);
		}
		TEST_METHOD(TestMethod14)
		{
			auto res = Solution().primePalindrome(930);
			AssertEx(10301, res);
		}