使用递归查找一个数是素数还是非素数的Python程序

素数，又称质数，指在大于1的自然数中，除1和它本身外，无法被其他自然数整除的数。在许多算法中都需要判断一个数是否是素数。下面我们来看看如何使用递归查找一个数是素数还是非素数的Python程序。

判断素数函数

首先，我们需要实现一个判断素数的函数。我们可以使用试除法来判断一个数是否是素数。而试除法就是依次将该数除以2到该数的平方根中的每一个数，如果存在一个数可以整除该数，那么该数就不是素数，反之，则是素数。这里我们使用递归来实现函数：

def is_prime(n, i=2):
    """
    递归判断一个数是否是素数
    n: int，待判断的数
    i: int，初始为2，从2开始试除
    return: bool，True表示是素数，False表示不是素数
    """
    if n <= 2:
        return n == 2
    if n % i == 0:
        return False
    if i * i > n:
        return True
    return is_prime(n, i+1)

上面的代码中，我们设置了两个参数，n代表待判断的数，i代表从多少数开始试除，默认为2。在函数内部，我们先判断如果n小于或等于2，则只有当n等于2时才是素数，否则就不是素数。然后我们试除n和i，如果发现n能被i整除，那么n就不是素数。如果i*i大于n，也就是n没有能整除的因子，那么n就是素数。否则，我们递归地调用is_prime函数，令i加1。

测试函数

接着我们来测试上面的函数。这里我们通过一个输入循环不断等待用户输入一个整数，并输出是否是素数。输入一个负数则退出程序。代码如下：

while True:
    try:
        n = int(input("请输入一个整数："))
        if n < 0:
            print("程序结束！")
            break
        if is_prime(n):
            print("是素数")
        else:
            print("不是素数")
    except ValueError:
        print("您输入的不是整数，请重新输入！")

上面的代码中，我们使用无限循环来等待用户输入整数。如果输入的整数是负数，那么退出程序。如果输入的不是整数，那么捕获到ValueError异常，提示用户重新输入。如果输入的是整数，那么判断是否是素数，是素数则输出“是素数”，反之则输出“不是素数”。

完整代码

最终的代码如下：

def is_prime(n, i=2):
    """
    递归判断一个数是否是素数
    n: int，待判断的数
    i: int，初始为2，从2开始试除
    return: bool，True表示是素数，False表示不是素数
    """
    if n <= 2:
        return n == 2
    if n % i == 0:
        return False
    if i * i > n:
        return True
    return is_prime(n, i+1)

while True:
    try:
        n = int(input("请输入一个整数："))
        if n < 0:
            print("程序结束！")
            break
        if is_prime(n):
            print("是素数")
        else:
            print("不是素数")
    except ValueError:
        print("您输入的不是整数，请重新输入！")