输出1~20000内的所有素数,按每行5个打印出来欧式筛
时间: 2024-09-17 09:06:20 浏览: 66
输入整数n,输出1~n的素数
输出1到20000之间的所有素数并按照每行5个的方式打印,可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes),这是一种古老的寻找范围内所有质数的经典算法。以下是步骤:
1. 创建一个布尔数组isPrime[20001],初始化所有元素为true,表示从2到20000的所有数字都是潜在的素数。
2. 从第一个质数2开始,将所有2的倍数标记为非素数(isPrime[2*2..n]=false)。
3. 找到下一个未被标记为非素数的数(这里是3),它是下一个质数,然后将它的所有倍数标记为非素数(如isPrime[3*3..n]=false)。
4. 重复这个过程,直到当前检查的数大于√20000,因为超过这个数的因子已经在之前的步骤中处理过了。
5. 最后,遍历isPrime数组,找出所有索引为true的元素,它们就是范围内的素数。
下面是伪代码示例:
```python
def print_primes():
limit = 20000
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i*i, limit+1, i):
is_prime[j] = False
count = 0
for i in range(2, limit + 1):
if is_prime[i]:
print(i, end=' ')
count += 1
if count % 5 == 0:
print() # 每打印5个数换一行
print_primes()
```
阅读全文