python如何编程求素数

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

python如何编程求素数
(图片来源网络,侵删)

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求解素数的两种常见方法,这两种方法都很简单易懂,但在实际使用时,需要根据具体的需求和场景选择合适的方法。

原创文章,作者:未希,如若转载,请注明出处:https://www.kdun.com/ask/469777.html

本网站发布或转载的文章及图片均来自网络,其原创性以及文中表达的观点和判断不代表本网站。如有问题,请联系客服处理。

(0)
未希新媒体运营
上一篇 2024-04-13 14:28
下一篇 2024-04-13 14:30

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

产品购买 QQ咨询 微信咨询 SEO优化
分享本页
返回顶部
云产品限时秒杀。精选云产品高防服务器,20M大带宽限量抢购 >>点击进入