用Python输入m,用回溯法输出所有的m位超级素数

在Python中，超级素数是指除了1和本身以外没有其他正因子的大于1的整数。使用回溯法寻找特定位数的超级素数需要递归地生成并检查每个可能的组合。这里是一个简单的示例，展示如何编写一个函数来查找m位的超级素数：

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_super_primes(m):
    def backtrack(num=0, prefix=""):
        if len(prefix) == m and is_prime(int(prefix)):
            super_primes.append(prefix)
        elif len(prefix) < m:
            for digit in "2357":
                # 只考虑非质数作为分隔数字，因为它们不会破坏超级素数属性
                if prefix and is_prime(int(prefix) * 10 + int(digit)):
                    backtrack(num + 1, prefix + str(digit))

    super_primes = []
    backtrack()
    return super_primes

# 获取所有m位的超级素数
m = int(input("请输入你要找的位数m："))
super_primes = generate_super_primes(m)
print(f"长度为{m}位的所有超级素数有：")
for prime in super_primes:
    print(prime)