输入一个正整数n，求不大于n的质数有多少个

输入一个正整数n，求不大于n的质数有多少个。

解法：使用筛法求解。先将2~n的数全部标记为质数，然后从2开始，将其所有的倍数标记为合数，依次类推，直到n。最后统计标记为质数的个数即可。

代码如下：

def count_primes(n):
    is_prime = [True] * (n+1)
    cnt = 
    for i in range(2, n+1):
        if is_prime[i]:
            cnt += 1
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return cnt

时间复杂度为O(nloglogn)。

相关问题

输入正整数n求不大于n的全部质数python

为了编写一个Python程序，用于输入一个正整数n并找出所有小于或等于n的质数，我们可以使用著名的埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种通过遍历从2到n的数字，并标记其倍数作为非质数的方法。以下是简单的实现：

def find_primes(n):
    # 初始化一个布尔列表，所有元素都设为True表示它们都是潜在的质数
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False  # 0和1不是质数

    # 遍历从2开始到sqrt(n)，将每个素数的倍数标记为非质数
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):  # 跳过已标记的非质数
                primes[j] = False

    # 返回大于1且为真的索引，即质数
    return [i for i in range(2, n+1) if primes[i]]

# 示例使用
n = int(input("请输入一个正整数: "))
result = find_primes(n)
print(f"小于等于{n}的所有质数有：{result}")

输入一个正整数 n, 求不大于n的所有素数的和的代码

以下是代码：

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

n = int(input("请输入正整数 n: "))
print("不大于n的所有素数的和为:", sum_of_primes(n))

希望对你有帮助。