python怎么判断是否为质数

  • Post category:Python

判断一个数是否为质数是Python编程中常见的问题。下面给出两种判断质数的方法:

方法一:试除法

试除法是最原始的一种判断质数的方法,思路是从 2 到 n-1,依次去除该数,如果不能被整除,则该数为质数。代码如下:

def is_prime(num):
    """
    判断一个数是否为质数
    """
    if num <= 1:
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

方法二:开平方法

在试除法的基础上,可以对循环的范围进行优化,因为一个数不可能被大于其平方根的数整除。代码如下:

import math

def is_prime(num):
    """
    判断一个数是否为质数
    """
    if num <= 1:
        return False
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

以上两种方法都可以用来判断一个数是否为质数,第二种方法在时间复杂度上略优于第一种。