博客

python怎么判断是否为质数

  • Post category:Python

当我们需要判断一个数字是否是质数的时候，我们可以借助于Python的循环语句和条件语句来实现。下面是Python判断质数的完整攻略：

什么是质数？

质数又称素数，指在大于1的自然数中，除了1和本身外，无法被其他自然数整除的数。

判断质数的常见方法

  1. 循环判断：从2开始，到该数减1为止，没有能整除该数的数，则该数为质数
  2. 质数判别法：根据数学定理计算，但实际应用中不太常用

代码实现

循环判断

通过循环判断，可以依次检查该数是否能够被小于该数的正整数整除，若都不能整除，则判断该数为质数。下面是一个循环判断质数的Python代码实例：

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

# 测试
print(is_prime(17)) # True
print(is_prime(27)) # False

上述代码中，我们定义了一个名为is_prime的函数，用于判断一个整数是否是质数。函数的参数为num，表示待判断的整数。在函数中，我们先判断num是否小于等于1，若小于等于1，则直接返回False，因为1以下的整数均不是质数。

接下来，我们使用for循环从2到num-1遍历所有可能的整数。在循环过程中，若发现num能够被其中一个整数整除，就意味着num不是质数，返回False。如果num不能被任何一个小于num的正整数整除，则认为num是一个质数，返回True。

最后，我们调用is_prime函数进行测试。可以看到，对于一个质数17，该函数返回True；而对于一个非质数27，该函数返回False。

优化算法

对于一个大于2的整数，如果它不能同时被2和3整除，那么它一定不能被大于√n的整数整除。基于这一点，我们可以在循环中每次减2，不必考虑偶数，缩短循环时间。

import math

def is_prime_better(num):
    if num <= 2:
        return num == 2
    if num % 2 == 0 or num % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(num))+1, 6):
        if num % i == 0 or num % (i+2) == 0:
            return False
    return True

# 测试
print(is_prime_better(17)) # True
print(is_prime_better(27)) # False

上述代码中，我们重新定义了一个名为is_prime_better的函数，用于判断一个整数是否是质数。在函数中，我们首先特判了num为小于等于2的情况，如果num等于2，返回True；否则，如果num是偶数或者能被3整除，返回False。

接下来，我们使用一个for循环，从5开始，每次加6遍历整数，判断num是否能够被其中一个整数或者该整数加2整除。在循环结束后，如果num不能被任何一个小于等于sqrt(num)的正整数整除，则认为num是一个质数，返回True。

这种优化算法的效率比循环判断高得多。

Tags: