素数回文数的个数

GitHub跳转原题关系图返回列表

枚举区间整数，同时检查试除素性和字符串回文性。

OJ: noi_openjudge

题目 ID: ch0113-05

难度:入门

标签:素数回文枚举python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
    1. 复杂度
    2. 总结

题意

统计 11 到 nn 之间既是素数又是回文数的整数个数。

思路

范围小于 1000，直接枚举即可。试除到平方根判断素数，text == text[::-1] 判断回文，同时满足就计数。

代码

Python代码

python
limit = int(input())


def is_prime(number: int) -> bool:
    if number < 2:
        return False
    for divisor in range(2, int(number**0.5) + 1):
        if number % divisor == 0:
            return False
    return True


count = sum(
    is_prime(number) and str(number) == str(number)[::-1]
    for number in range(11, limit + 1)
)
print(count)

复杂度

时间复杂度为 O(nn)O(n\sqrt n)，空间复杂度为 O(1)O(1)。

总结

小范围题中，清晰的直接枚举通常优于复杂预处理。