当先锋百科网

首页 1 2 3 4 5 6 7

质数,即只能被1和它本身整除的数。在数学中,质数有着重要的地位。因为质数无法再分解成其他数相乘的形式,所以在密码学等方面有着广泛的应用。今天,我们就来看看如何使用Python求质数个数。


def count_prime_numbers(n: int) -> int:
    if n < 2:
        return 0
    
    primes = [True] * n
    primes[0] = primes[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(i * i, n, i):
                primes[j] = False
                
    return sum(primes)

python求质数个数

上面的代码实现了一个求质数个数的函数,它的原理是利用筛法来筛选质数。我们先将所有数标记为质数,然后从2开始筛选,筛掉它的所有倍数并标记为非质数,最终剩下的就是所有的质数。然后我们再统计True的个数即可。

首先,在函数中我们接收一个整数n作为参数,表示要求1到n之间的质数个数。

然后,我们判断如果n小于2,那么就不存在质数,直接返回0。

接着,我们创建一个长度为n的列表primes,并将所有数都标记为True,表示它们是质数。我们将primes[0]和primes[1]标记为False,因为1和0都不是质数。

然后,我们从2开始遍历到n的平方根,如果遇到了一个质数i,那么我们就从i的平方开始,将i的所有倍数都标记为非质数。

最后,我们使用Python内置函数sum来统计primes中True的个数,也就是质数的个数,然后将结果返回。

现在,我们来测试一下这个函数:


print(count_prime_numbers(10)) # 4个质数
print(count_prime_numbers(100)) # 25个质数
print(count_prime_numbers(1000)) # 168个质数

输出结果为:


4
25
168

我们可以看出,输出结果与我们的预期相符,说明函数实现正确。