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中，计算一定范围内的质数个数可以通过编写一个函数来实现，这个函数通常会遍历指定区间，检查每个数字是否为质数。以下是简单的步骤和代码示例：

1. 定义一个函数`is_prime(n)`，它接收一个整数n作为输入，判断n是否为质数。如果n小于2，则不是质数；如果n等于2，它是质数；大于2的数需要从2到其平方根（因为大于该数的因子必然有一个小于它的平方根）逐一检查是否有因数。

def is_prime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

2. 写一个主函数，如`count_primes(start, end)`，接受起始和结束值，然后迭代并计数质数。

def count_primes(start, end):
    prime_count = 0
    for num in range(start, end+1):
        if is_prime(num):
            prime_count += 1
    return prime_count

你可以像下面这样调用这个函数：

start = 1
end = 100  # 想要计算1到100之间的质数个数
print(f"在 {start} 到 {end} 的范围内，有 {count_primes(start, end)} 个质数.")

Python计算素数的函数

Python中有多种方法可以编写计算素数的函数，这里我会介绍一种常见的简单算法，即“埃拉托斯特尼筛法”（Sieve of Eratosthenes）。这个方法适合用于查找一定范围内的所有素数。

def is_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2  # 跳过偶数，因为除了2以外，素数都是奇数
    return True

def primes_sieve(limit):
    primes = [True] * (limit + 1)
    primes[0], primes[1] = False, False
    for num in range(2, int(limit**0.5) + 1):
        if primes[num]:
            for multiple in range(num*num, limit + 1, num):
                primes[multiple] = False
    return [i for i, prime in enumerate(primes) if prime]

# 使用示例
print(primes_sieve(30))  # 输出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]