生成特殊N位质数 - 算法题解 - 常规

生成特殊N位质数 - 算法题解

问题描述

给定一个整数N（2 <= N <= 8），生成所有的具有下列特性的特殊的N位质数，即其前任意位都是质数。例如，7331即是这样一个4位的质数，因为7、73和733也都是质数。

输入形式

输入一个整数N（2 <= N <= 8）。

输出形式

输出有若干行，每行有一个整数，该整数有N位，而且其前任意位都是质数。并且：

要求输出所有符合题意的质数。
从小到大按顺序输出，且所有行上的数字不得重复。

样例输入

样例输出

样例输入

样例输出

样例说明

样例一中，符合条件的3位质数有2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97。

所以，我们可以先枚举第一位，然后从2, 3, 5, 7中选出第二位，然后从所有前两位都是质数的数中选出第三位，最后判断是否是质数即可。

算法思路

首先我们需要判断一个数是否是质数，可以使用简单的判断方法：从2开始，一直到该数的平方根，逐个判断该数是否能被整除，如果能被整除，则该数不是质数。
我们可以使用递归的方法来生成所有符合条件的N位质数：
- 当N为1时，直接输出所有一位质数（2, 3, 5, 7）。
- 当N大于1时，枚举第一位数字（2, 3, 5, 7），然后递归生成所有符合条件的(N-1)位质数，最后判断生成的N位数是否是质数。

代码实现

# 判断一个数是否是质数
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

# 生成所有符合条件的N位质数
def generate_primes(n):
    if n == 1:
        for i in [2, 3, 5, 7]:
            print(i)
    else:
        for i in [2, 3, 5, 7]:
            for j in generate_primes(n-1):
                num = int(str(i) + str(j))
                if is_prime(num):
                    print(num)

# 输入N
n = int(input())
# 生成所有符合条件的N位质数
generate_primes(n)

总结

本题可以使用递归的方法来生成所有符合条件的N位质数，代码实现较为简单。需要注意的是，需要先判断一个数是否是质数，可以使用简单的判断方法：从2开始，一直到该数的平方根，逐个判断该数是否能被整除，如果能被整除，则该数不是质数。