題目描述

因為 $151$ 既是一個質數又是一個回文數（從左到右和從右到左是看一樣的），所以 $151$ 是回文質數。

寫一個程序來找出范圍 $[a,b](5\le a<b\le 100,000,000)$（一億）間的所有回文質數。

輸入格式

第一行輸入兩個正整數 $a$ 和 $b$。

輸出格式

輸出一個回文質數的列表，一行一個。

輸入輸出樣例

輸入

5 500

輸出

5
7
11
101
131
151
181
191
313
353
373
383

方式

代碼

class Solution:@staticmethoddef oi_input():"""從標準輸入讀取數據"""left, right = map(int, input().split())return left, right@staticmethoddef oi_test():"""提供測試數據"""return 5, 500@staticmethoddef solution(left, right):def is_prime(n):'''試除法，優化版'''if n < 2:return Falseif n in (2, 3):return Trueif n % 2 == 0 or n % 3 == 0:return Falsei, w = 5, 2while i * i <= n:  # i 為除數 所以要不大于n的平方根if n % i == 0:return Falsei += ww = 6 - wreturn Truedef generate_palindromes():'''回文數生成'''yield 5yield 7yield 11for length in [3, 5, 7]:k = (length + 1) // 2start, end = 10 ** (k - 1), 10 ** k  # 左 與 右for num in range(start, end):s = str(num)if s[0] not in {'1', '3', '7', '9'}:  # 判斷最后一位continueprefix, suffix = s, s[:-1][::-1]  # 前半部分 與 去除了中間的后半部分pal = int(prefix + suffix)yield palprime_nums = []for pal in generate_palindromes():if left <= pal <= right and is_prime(pal):prime_nums.append(pal)for p in prime_nums:print(p)oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solutionif __name__ == '__main__':left, right = oi_test()# left, right = oi_input()solution(left, right)

流程圖