这是一道命令式编程操作数组的题目。 编写程序,找出1至n以内的所有素数。要求使用数组元素的下标从1至n以内表示这些数值,数组元素的值作为素数的标志。其中用数组元素的值为0来表示该元素的下标的数值是素数,用1来表示该元素的下标的数值不是素数,并输出这些素数。
时间: 2024-02-28 21:56:39 浏览: 53
输出1到n之间的素数
5星 · 资源好评率100%
好的,这是一道经典的素数筛选问题,我们可以使用埃氏筛法(Erathostenes Sieve)来解决。
具体实现步骤如下:
1. 创建一个长度为 n+1 的数组,初始值都为 0,用来标记每个数是否为素数。
2. 将数组下标为 0 和 1 的元素赋值为 1,因为它们不是素数。
3. 从 2 开始遍历到 n,如果当前元素的值为 0,说明它是素数,将它的倍数(除了自己)的元素标记为 1。
4. 遍历整个数组,输出值为 0 的元素的下标。
下面是实现代码:
```python
def find_primes(n):
is_prime = [0] * (n + 1)
is_prime[0] = is_prime[1] = 1
for i in range(2, n + 1):
if is_prime[i] == 0:
# i 是素数,标记它的倍数
j = 2 * i
while j <= n:
is_prime[j] = 1
j += i
# 输出素数
primes = []
for i in range(2, n + 1):
if is_prime[i] == 0:
primes.append(i)
print(i, end=' ')
return primes
```
我们可以调用这个函数来找出 1 到 n 的所有素数,比如:
```python
primes = find_primes(100)
```
这样就可以找出 1 到 100 的所有素数,并将它们输出。同时,函数还会返回一个素数列表,方便后续程序的处理。
阅读全文