算法leetcode

力扣866-回文素数

字数统计: 705字   |   阅读时长: 3分
,

摘要: 力扣 866-回文素数。构造回文+素性测试。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个题，算是素性测试的应用。此外本题枚举回文串的过程也是一个难点，值得学习。

题目

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

提示：

1
2
1 <= N <= 1e8
答案肯定存在，且小于 2 * 1e8。

示例 1：
输入：6
输出：7

示例 2：
输入：8
输出：11

示例 3：
输入：13
输出：101

题解

算法：构造回文+素数测试

整体的算法思路就是枚举所有回文数，然后进行素性测试。

素性测试就用试除法即可：枚举 $[2, \sqrt{n}]$ 之间的数，判断是否能整除 n。

本题比较难的一点在于如何不重不漏地枚举所有回文数。

对于一个长度为 d 的回文串，它的前 $l = (d+1)/2$ 个数字构成一个回文根。例如：12321 的回文根是 123、123321 的回文根是 123。

一个回文根对应两个回文串，一个奇数长度、一个偶数长度。例如回文根 111，对应 11111、111111 两个回文数。

因此我们可以枚举大小满足要求每个回文根，然后构造对应的奇数长度和偶数长度的回文数，对于 l 长度的回文根，有长度为 2l 和 2l - 1 的两个回文数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    int primePalindrome(int N) {
        string N_str = to_string(N);
        int len = (N_str.size() + 1) / 2; // 回文根初始长度
        for(int l = len; l <= 5; ++l)
        {
            int start = pow(10, l - 1);
            // 查 2l-1 长的
            for(int r = start; r < pow(10, l); ++r)
            {
                string r_str = to_string(r);
                string p_str = r_str;
                auto it = ++r_str.rbegin();
                while(it != r_str.rend())
                {
                    p_str += *it;
                    ++it;
                }
                stringstream ss2;
                int nxt;
                ss2 << p_str;
                ss2 >> nxt;
                if(nxt >= N && isPrime(nxt))
                    return nxt;
            }
            // 查 2l 长的
            for(int r = start; r < pow(10, l); ++r)
            {
                string r_str = to_string(r);
                string p_str = r_str;
                auto it = r_str.rbegin();
                while(it != r_str.rend())
                {
                    p_str += *it;
                    ++it;
                }
                stringstream ss2;
                int nxt;
                ss2 << p_str;
                ss2 >> nxt;
                if(nxt >= N && isPrime(nxt))
                    return nxt;
            }
        }
        return -1;
    }

private:
    bool isPrime(int n)
    {
        if(n == 1)
            return false;
        for(int i = 2; i * i <= n; ++i)
            if(n % i == 0)
                return false;
        return true;
    }
};
Share