python计算素数个数

以下是一个计算素数个数的 Python 代码示例:

def count_primes(n):
    """
    计算小于等于n的素数个数
    """
    # 初始化一个数组表示小于等于n的所有数是否为素数，默认都是素数
    is_prime = [True] * (n+1)
    count = 0  # 计数器，统计素数个数
    for i in range(2, n+1):
        if is_prime[i]:  # 如果i是素数
            count += 1  # 计数器加1
            # 将i的倍数标记为非素数
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return count

使用示例:

n = 100
print("小于等于", n, "的素数个数是", count_primes(n))

输出结果:

小于等于 100 的素数个数是 25

相关问题

Python快速计算输出素数个数

以下是一个Python程序，用于计算给定范围内的素数个数：

def count_primes(n):
    """
    计算小于 n 的素数个数
    """
    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]:
            primes[i*i:n:i] = [False] * ((n - 1 - i*i) // i + 1)
    return sum(primes)

print(count_primes(100))  # 输出25，小于100的素数个数为25个

该程序使用了筛法求素数的思想，时间复杂度为 $O(n\log\log n)$。

python素数个数

以下是一个简单的 Python 代码，用于计算从 1 到指定数字的素数个数。

def count_primes(n):
    if n < 2:
        return 0
    primes = [2]
    for i in range(3, n+1, 2):
        if all(i % p != 0 for p in primes):
            primes.append(i)
    return len(primes)

使用该函数，您可以计算从 1 到任意数字的素数个数，例如：

>>> count_primes(10)
4
>>> count_primes(20)
8
>>> count_primes(100)
25