python判断质数的方法有哪些

54次阅读
没有评论

共计 774 个字符,预计需要花费 2 分钟才能阅读完成。

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

  1. 简单的方法是遍历从 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
  1. 优化的方法是只需要遍历从 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
  1. 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

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

丸趣 TV 网 – 提供最优质的资源集合!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-12-22发表,共计774字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)