首页输入正整数n输出n以内的全部素数，并输出n以内所有素数的个数

输入正整数n输出n以内的全部素数，并输出n以内所有素数的个数

时间: 2024-12-02 19:18:28 浏览: 95

当需要编写程序找出某个正整数n以内的所有素数并计算它们的数量时，我们可以采用经典的“埃拉托斯特尼筛法”（Sieve of Eratosthenes）算法。这个算法的基本步骤如下： 1. 创建一个布尔数组`isPrime[0...n]`，初始化所有的元素为`true`，表示从2到n的所有数字都是潜在的素数。 2. 从第一个质数2开始，将`isPrime[2]`设置为`false`，因为2是唯一的偶数质数。 3. 遍历数组，对于每个索引i（如果它是质数），将它的所有倍数标记为非质数，即`isPrime[i*j] = false`（j从2开始，因为i的倍数已经包含了i本身）。 4. 遍历结束后，数组中未被标记为`false`的元素就是素数。计数这些`true`值即可得到素数的个数。下面是伪代码示例： ```python def sieve_of_eratosthenes(n): isPrime = [True] * (n + 1) count = 0 for i in range(2, int(n**0.5) + 1): # 只需遍历到√n if isPrime[i]: count += 1 # 统计素数 for j in range(i*i, n+1, i): # 标记其倍数为非素数 isPrime[j] = False return isPrime, count # 示例：获取50以内的素数和个数 primes, prime_count = sieve_of_eratosthenes(50) print("50以内的素数有:", primes) print("素数个数: ", prime_count) ```

阅读全文