python如何编程求素数

素数是只有两个正因数（1和它本身）的自然数，例如2、3、5、7等，在Python中，我们可以使用一些简单的算法来求解素数，以下是两种常见的方法：埃拉托斯特尼筛法（Sieve of Eratosthenes）和厄拉多塞筛法（Sieve of Eratosthenes）。

1、埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种古老的寻找素数的方法，其基本思想是从2开始，将2的倍数剔除，然后找到下一个未被剔除的数，将其倍数剔除，如此循环，直到遍历完所有小于等于给定数的数。

以下是使用埃拉托斯特尼筛法求解素数的Python代码：

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
print(sieve_of_eratosthenes(100))

在这段代码中，我们首先创建了一个布尔数组is_prime，用于标记每个数是否为素数，我们从2开始，将所有2的倍数标记为非素数，接着，我们找到下一个未被标记为非素数的数，将其倍数标记为非素数，如此循环，直到遍历完所有小于等于给定数的数，我们返回所有被标记为素数的数。

2、厄拉多塞筛法

厄拉多塞筛法是一种改进的埃拉托斯特尼筛法，其主要思想是先找到小于等于给定数的所有素数，然后从大到小依次剔除合数，这种方法的优点是可以更快地找到素数。

以下是使用厄拉多塞筛法求解素数的Python代码：

def sieve_of_eratosthenes(n):
    primes = []
    mark = [False] * (n + 1)
    for i in range(2, n + 1):
        if mark[i] == False:
            primes.append(i)
            mark[i] = True
            for j in range(i, n + 1, i):
                mark[j] = True
    return primes[::1]
print(sieve_of_eratosthenes(100))

在这段代码中，我们首先创建了一个布尔数组mark，用于标记每个数是否已被标记为合数，我们从2开始，将所有2的倍数标记为合数，接着，我们找到下一个未被标记为合数的数，将其及其倍数标记为合数，如此循环，直到遍历完所有小于等于给定数的数，我们将所有被标记为素数的数逆序返回。

以上就是使用Python求解素数的两种常见方法，这两种方法都很简单易懂，但在实际使用时，需要根据具体的需求和场景选择合适的方法。

网页名称：python如何编程求素数
URL链接：http://www.shufengxianlan.com/qtweb/news47/326447.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联