python判断质数的方法有哪些-开发者知识库平台

python判断质数的方法有哪些

python

1218

2023/11/10 22:00:06

栏目: 编程语言

判断质数的方法有以下几种：

简单的方法是遍历从2到n-1的所有整数，判断n是否能被这些整数整除。如果n能被任何一个整数整除，则n不是质数。这种方法的时间复杂度为O(n)。

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

优化的方法是只需要遍历从2到n的平方根的整数即可。因为如果n能被大于其平方根的整数整除，那么一定能被小于其平方根的整数整除。同样，如果n不能被小于其平方根的整数整除，那么一定不能被大于其平方根的整数整除。时间复杂度为O(sqrt(n))。

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

Sieve of Eratosthenes（埃拉托色尼筛选法）是一种筛选法，用于找出一定范围内的所有质数。具体步骤是从2开始，将所有能被2整除的数标记为非质数，然后找到下一个未被标记的数，将其作为质数，并将其倍数标记为非质数，重复这个过程直到所有数都被标记。时间复杂度为O(nloglogn)。

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return primes

这些方法可以根据具体情况选择使用。如果只需要判断一个数是否为质数，可以使用第一种或第二种方法。如果需要找出一定范围内的所有质数，可以使用第三种方法。

辰迅云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

python判断质数的方法有哪些

最新知识库

相关标签