如何判断一个数是否是质数?

首先,解释什么是质数:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数。

  那么我们可以采用的方法是,将这个数除2到这个数本身减一,如果这其中除某个数,余数为零,那么这个数就可以判定为非质数(合数),否则就为质数。

  至于为什么要从2开始除,这就是一个简单的数学问题了,因为能被1和本身其他自然数整除的数为质数,那么我们只需实验能否被1和此数本身之间的自然数整除。自然数:即非负数的整数。

  那么我们可以采用python编写一个小示例来检验一个数是否为质数:

def isPrime(number):
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

  调用函数实验一下,分别用合数10和质数107调用函数:

  然而,这种方式是将i遍历了2到数本身-1,实际不需要如此。当一个数除以比这个数的一半还要大的数时,得到的值就已经是小于2了的非自然数,所以让这个数去除以大于本身一半的数来验证是否有自然数的值是不合理的。所以我们只需要让这个数除以2到本身一半的数来验证是否是质数。于是,代码可以改进提高运行性能:

def isPrime(number):
    for i in range(2, number//2):
        if number % i == 0:
            return False
    return True

  结果如上。需注意的是,在第二行range()函数中,只让i遍历2到number//2-1,是因为,不需要让i等于这个数的一半,因为让这个数除以自身一半的数等于2,那么在i=2时就已经可以判定是否为质数了。

如果无法查看博客中的图片,请挂代理访问,因为图片是存储在GitHub上的。
原文地址:https://www.cnblogs.com/ahaolee/p/10452851.html