Python题目 - 回文质数

发表于 更新于 分类于 阅读次数： 阅读次数：

题目描述

因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a,b] $(5 \le a < b \le 100,000,000)$ (一亿)间的所有回文质数。

输入格式

第 1 行: 二个整数 a 和 b .

输出格式

输出一个回文质数的列表，一行一个。

输入输出样例

输入

1
5 500

输出

1
2
3
4
5
6
7
8
9
10
11
12
5
7
11
101
131
151
181
191
313
353
373
383

超时实现

1
2
3
4
5
6
7
8
9
10
11
12
# 获得输入
ab = input().split()
a = int(ab[0])
b = int(ab[1])
for i in range(a, b + 1):
    if i % 2 == 1:
        if str(i)[::-1] == str(i): # 判断是否回文数
            for j in range(2, int(i ** 0.5) + 1): # 判断是否质数
                if i % j == 0:
                    break
            else:
                print(i) # 是则打印

大佬方法

埃氏筛

1
2
3
4
5
6
7
8
9
10
def prime_numbers(n):
    number = [1]*(n+1)  # 初始化，1表示全部为质数
    for i in range(2, int((n**0.5))+1):
        if number[i]:  # 如果下标i对应的数字i是素数
            for j in range(i*i, n+1, i):  # 素数i的各个倍数
                number[j] = 0
                j += 1
    for x in range(2, n+1):
        if number[x]:
            print(x)