用筛选法求素数,输出1000之内所有的素数,并统计个数。
时间: 2024-11-12 17:41:34 浏览: 19
筛选法,也叫埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种用于寻找一定范围内所有素数的传统算法。以下是基本步骤:
1. 创建一个从2开始,长度为1000的布尔数组(isPrime),并将所有元素初始化为true。这是为了表示这1000以内每个数都是潜在的素数。
2. 从第一个素数2开始,遍历数组。对于每一个素数i,找到它在isPrime数组中的位置,然后将从i的平方数开始的所有后续数标记为合数(isPrime[i*j] = false)。因为所有能被i整除的数都不可能是素数。
3. 继续这个过程,直到遇到下一个还未被标记为合数的数。例如,下一个未标记的数就是下一个素数,继续更新isPrime数组。
4. 遍历完整个数组后,剩下的所有值为true的索引对应的数字就是1000以内的素数。
5. 计算素数的数量,只需统计isPrime数组中值为true的元素个数即可。
```python
def sieve_of_eratosthenes(n):
is_prime = [True] * (n+1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5)+1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
primes = [i for i, prime in enumerate(is_prime) if prime]
return primes, len(primes)
# 调用函数获取1000以内的素数列表和个数
primes, count = sieve_of_eratosthenes(1000)
print("1000以内的素数有:", primes)
print("共有", count, "个素数")
```
阅读全文