博客

python写一判素数的函数

  • Post category:Python

下面是用Python编写一判素数的函数的详细攻略：

1. 确定函数名和参数

首先，我们需要为这个函数取个名字，通常命名规范是用动词+名词的形式，比如 is_prime。接下来，我们需要确定这个函数需要接收哪些参数，肯定是一个整数。因此，我们的函数定义应该是这样的：

def is_prime(n: int):
    # 函数体暂时留空

2. 判断素数的思路及代码实现

判断素数的方法有很多种，这里我们介绍两种比较常见的方法：

方法一：枚举法

素数是只能被1和自己整除的正整数。因此，我们可以通过枚举2到n-1之间的每一个正整数，判断n是否能被它们整除，如果能，那么n就不是素数，反之就是素数。

这种方法虽然简单易懂，但是比较低效，时间复杂度为O(n)。下面是这种方法的代码实现：

def is_prime(n: int):
    if n <= 1:   # 1不是素数
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

方法二：试除法

试除法又称质因数分解法，它的思路是如果一个数n不是素数，那么它一定可以被分解成几个质数（即只有1和它本身这两个因数）的乘积。为了提高效率，我们只需要试除小于等于n的正整数的质数，如果没有质因数，那么n就是素数了。

这种方法比枚举法效率高，时间复杂度为O(n^1/2)。下面是试除法的代码实现：

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

3. 完整代码及测试

综合上述两种方法，完整代码如下：

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

# 测试
print(is_prime(7))   # True
print(is_prime(10))  # False
print(is_prime(1))   # False

我们可以通过这个测试代码来验证我们的判素数函数是否正确。

Tags: