python写一判素数的函数

  • Post category:Python

要编写一个判素数的函数,我们需要明确什么是素数。素数指的是只能被1和它本身整除的正整数。

下面是一个简单的Python代码示例,用于判断一个数字是否为素数:

def is_prime(number):
    # 0和1不是素数
    if number < 2:
        return False
    # 判断是否能被2到number-1之间的数字整除
    for i in range(2, number):
        if number % i == 0:
            return False
    # 如果不被整除则是素数
    return True

这个函数以一个整数作为参数并返回一个布尔值。如果输入的数字是素数,则返回True,否则返回False。

首先,如果数字小于2,则它不是素数,因此我们可以立即返回False。

然后,我们使用for循环遍历2到数字减1之间的所有数字。如果数字能够被其中的任何一个数字整除,则说明它不是素数。然后返回False。

最后,如果数字不能被任何数字整除,则说明它是素数并返回True。

下面是另一个示例函数,它使用更有效的算法来检查素数。这种方法称为试除法:

def is_prime_v2(number):
    if number < 2:
        return False
    # 检查2和3
    if number == 2 or number == 3:
        return True
    # 如果是偶数或3的倍数,则不是素数
    if number % 2 == 0 or number % 3 == 0:
        return False
    # 检查开头和结尾
    start = 5
    end = int(number ** 0.5) + 1
    for i in range(start, end, 6):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True

同样,这个函数以一个整数作为参数并返回一个布尔值。首先,如果数字小于2,则返回False。

然后,我们检查数字是否等于2或3,因为它们是素数。如果是,则返回True。

否则,我们检查数字是否为偶数或3的倍数,因为它们也不是素数。如果是,则返回False。

现在,我们要检查的数字既不是偶数也不是3的倍数,并且大于3。因此,我们可以从5开始,每次以6为步长逐个检查数字。这是因为,我们可以快速判断一些数字是否为素数,这些数字可以表示为6n+1或6n-1的形式。例如,5可以表示为6×1-1,7可以表示为6×1+1,11可以表示为6×2-1,13可以表示为6×2+1,以此类推。

我们只需要检查刚刚计算出来的开头和结尾区间内的数字。如果数字能被其中一个整除,则它不是素数并返回False。如果数字不能被任何数字整除,则它是素数,并返回True。

以上是判断素数的两个示例函数,两种方法各有优缺点。我们可以根据需要选择更适合的方法或者组合使用。