质数,即只能被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)
上面的代码实现了一个求质数个数的函数,它的原理是利用筛法来筛选质数。我们先将所有数标记为质数,然后从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
我们可以看出,输出结果与我们的预期相符,说明函数实现正确。