03247: 回文素数

http://cs101.openjudge.cn/practice/03247/

一个数如果从左往右读和从右往左读数字是相同的，则称这个数是回文数，如121，1221，15651都是回文数。给定位数n，找出所有既是回文数又是素数的n位十进制数。（注：不考虑超过整型数范围的情况）。

输入

位数n,其中1<=n<=9。

输出

第一行输出满足条件的素数个数。第二行按照从小到大的顺序输出所有满足条件的素数，两个数之间用一个空格区分。

样例输入

样例输出

4
2 3 5 7

python

import math

def is_prime(num):
    if num < 2:
        return False
    if num in {2, 3, 5, 7}:
        return True
    if num % 2 == 0 or num % 5 == 0:
        return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

def generate_palindromes(n):
    palindromes = []
    if n == 1:
        return [2, 3, 5, 7]  # 1位数的素数回文数

    half_len = (n + 1) // 2  # 只需要构造前半部分
    start, end = 10**(half_len - 1), 10**half_len
    
    for first_half in range(start, end):
        first_half_str = str(first_half)
        if n % 2 == 0:  # 偶数位
            palindrome = int(first_half_str + first_half_str[::-1])
        else:  # 奇数位
            #palindrome = int(first_half_str + first_half_str[-2::-1])
            palindrome = int(first_half_str + first_half_str[:-1][::-1])
        
        if is_prime(palindrome):
            palindromes.append(palindrome)
    
    return palindromes

def find_palindromic_primes(n):
    primes = generate_palindromes(n)
    print(len(primes))
    print(" ".join(map(str, primes)))

# 输入
n = int(input().strip())
find_palindromic_primes(n)

03247: 回文素数 ​

03247: 回文素数