前端做网站直播,分公司一般做网站吗,被称为网页制作三剑客的是,南昌 网站 公司题目链接 Leetcode.866 回文质数 rating : 1938 题目描述
给你一个整数 n n n #xff0c;返回大于或等于 n n n 的最小 回文质数。
一个整数如果恰好有两个除数#xff1a; 1 1 1 和它本身#xff0c;那么它是 质数 。注意#xff0c; 1 1 1 不是质数。
例如#xf…题目链接 Leetcode.866 回文质数 rating : 1938 题目描述
给你一个整数 n n n 返回大于或等于 n n n 的最小 回文质数。
一个整数如果恰好有两个除数 1 1 1 和它本身那么它是 质数 。注意 1 1 1 不是质数。
例如 2 、 3 、 5 、 7 、 11 2、3、5、7、11 2、3、5、7、11 和 13 13 13 都是质数。
一个整数如果从左向右读和从右向左读是相同的那么它是 回文数 。
例如 101 101 101 和 12321 12321 12321 都是回文数。
测试用例保证答案总是存在并且在 [ 2 , 2 × 1 0 8 ] [2, 2 \times 10^8] [2,2×108] 范围内。
示例1 输入n 6 输出7 示例2 输入n 8 输出11 示例3 输入n 13 输出101 提示 1 ≤ n ≤ 1 0 8 1 \leq n \leq 10^8 1≤n≤108
解法数学 判断质数
对于 回文数 我们可以得出这么一个结论任何一个大于 11 11 11 的偶数长度的回文数一定是 11 11 11 的倍数。
证明如下 1 0 0 1 m o d 11 1 10 ^ 0 1 \ mod \ 11 1 1001 mod 111 1 0 1 10 m o d 11 10 10 ^ 1 10 \ mod \ 11 10 10110 mod 1110 1 0 2 100 m o d 11 1 10 ^ 2 100 \ mod \ 11 1 102100 mod 111 1 0 3 1000 m o d 11 10 10 ^ 3 1000 \ mod \ 11 10 1031000 mod 1110 1 0 4 10000 m o d 11 1 10 ^ 4 10000 \ mod \ 11 1 10410000 mod 111…
根据数学归纳法我们可以得出这样的结论 n n n 为偶数那么 1 0 n m o d 11 1 10 ^ n \ mod \ 11 1 10n mod 111 n n n 为奇数那么 1 0 n m o d 11 10 10 ^ n \ mod \ 11 10 10n mod 1110
假设回文数 P P P 一共有 2 n 2n 2n 位从高到低分别为 a 1 a 2 a 3 a 4 . . . a n a n a n − 1 . . . a 2 a 1 a_1a_2a_3a_4...a_na_na_{n-1}...a_2a_1 a1a2a3a4...ananan−1...a2a1。
将其转换为十进制的形式如下 P a 1 × 1 0 2 n − 1 a 2 × 1 0 2 n − 2 . . . a n × 1 0 n a n × 1 0 n − 1 . . . a 2 × 10 a 1 P a_1\times10^{2n-1}a_2\times10^{2n-2}...a_n\times10^na_n\times10^{n-1}...a_2\times10a_1 Pa1×102n−1a2×102n−2...an×10nan×10n−1...a2×10a1
如果对回文数 P P P 模 11 11 11我们可以得到如下的结果 P a 1 × 10 a 2 × 1 a 3 × 10 . . . a n × 10 a n × 1 . . . a 2 × 10 a 1 P a_1 \times 10 a_2\times1a_3\times10...a_n\times10a_n\times1...a_2\times10a1 Pa1×10a2×1a3×10...an×10an×1...a2×10a1
将其整理一下得到如下结果 P a 1 × 11 a 2 × 11 a 3 × 11 . . . a n × 11 P a_1 \times 11 a_2\times11a_3\times11...a_n\times11 Pa1×11a2×11a3×11...an×11
可以发现在对 P P P 模 11 11 11 的基础之上剩下的余数依旧是 11 11 11说明 11 11 11 可以整除 P P P也就是 P P P 是 11 11 11 的倍数。
根据以上的证明我们可以得出结论
如果 n ≤ 11 n \leq 11 n≤11那么只需要在 [ 2 , 11 ] [2, 11] [2,11] 中找到第一个大于等于 n n n 的质数返回即可。如果 n 11 n 11 n11因为偶数长度的回文数全都不是质数所以我们只需要判断奇数长度的回文数。由于是回文数所以我们只需要获取前一半后一半直接拼接上即可。所以只需要在 [ 10 , 19999 ] [10, 19999] [10,19999] 找到第一个大于等于 n n n 的回文质数 x x x 即可。
时间复杂度 O ( n 3 4 ) O(n^\frac{3}{4}) O(n43)
C代码
class Solution {
public:bool check(int x){if(x 2) return false;for(int i 2;i * i x;i){if(x % i 0) return false;}return true;}int primePalindrome(int k) {if(k 11){for(int i 2;i 11;i){if(i k check(i)) return i;}}else{for(int i 10;i 19999;i){string s to_string(i);int n s.size();for(int i n - 2;i 0;i--) s.push_back(s[i]);int x stoi(s);if(x k check(x)) return x;} }return -1;}
};Python3代码:
def check(x: int) - bool:if x 2:return Falsei 2while i * i x:if x % i 0:return Falsei 1return Trueclass Solution:def primePalindrome(self, k: int) - int:if k 11:for i in range(2, 12):if i k and check(i):return ielse:for i in range(10, 20000):s str(i)n len(s)s s s[:n - 1][::-1]x int(s)if x k and check(x):return xreturn -1
