AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 866. Prime Palindrome    原题链接    中等

作者: 作者的头像   wzc1995 ,  2019-01-15 12:53:10 ,  所有人可见 ,  阅读 1532


2


1

题目描述

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

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

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

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

例如,12321 是回文数。

样例

输入:6
输出:7
输入:8
输出:11
输入:13
输出:101

注意

  • 1 <= N <= 10^8
  • 答案肯定存在,且小于 2 * 10^8。

算法

(暴力枚举) $O(N)$
  1. 我们从最小的回文数开始逐一枚举,直到找到一个大于等于 N 的素数为止。
  2. 这里有一个结论,除 11 以外,偶数长度的回文数不可能是素数。这里用到了被 11 整除的数的性质,奇数位之和等于偶数位之和的数一定能被 11 整除。
  3. 枚举的过程可以使用技巧,我们枚举奇数长度回文数的前半部分,这样第一次遇到素数且大于 N 就可以停下了。

时间复杂度

  • 由于最多有 $O(\sqrt(N))$ 个数字需要枚举,每次判定素数需要 $O(sqrt(N))$ 的时间,故时间复杂度为 $O(N)$。

空间复杂度

  • 生成回文数时需要空间存放临时字符串,故空间复杂度为 $O(\log N)$。

C++ 代码

class Solution {
public:

    bool check(int x) {
        if (x < 2 || (x > 2 && x % 2 == 0))
            return false;
        for (int i = 3; i * i <= x; i += 2)
            if (x % i == 0)
                return false;
        return true;
    }

    int make(int x) {
        string s = to_string(x), t = s;
        reverse(t.begin(), t.end());
        s.pop_back();
        return stoi(s + t);
    }

    int primePalindrome(int N) {
        if (N > 7 && N <= 11)
            return 11;

        for (int i = 1; i <= 99999; i++) {
            int x = make(i);
            if (x >= N && check(x))
                return x;
        }

        return -1;
    }
};

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息