筛选法,也称为埃拉托斯特尼筛法,是一种用于找出一定范围内所有素数的方法。下面是使用筛选法求解100以内的素数的步骤:
1. **初始化:**
- 创建一个长度为 (N+1) 的布尔数组,初始值都设为 True。这个数组将表示从 0 到 (N) 是否为素数。
2. **开始筛选:**
- 从2开始,将2的所有倍数标记为 False,因为它们不是素数。
3. **继续筛选:**
- 找到下一个未被标记的数 (x),将 (x) 的所有倍数标记为 False。
4. **重复:**
- 重复步骤3,直到找不到更大的未被标记的数。
5. **输出素数:**
- 所有未被标记的数即为素数。
以下是一个Python代码示例,使用筛选法找出100以内的素数:
```python
def sieve_of_eratosthenes(limit):
primes = []
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for number in range(2, int(limit**0.5) + 1):
if is_prime[number]:
primes.append(number)
for multiple in range(number * number, limit + 1, number):
is_prime[multiple] = False
for number in range(int(limit**0.5) + 1, limit + 1):
if is_prime[number]:
primes.append(number)
return primes
# 找出100以内的素数
result = sieve_of_eratosthenes(100)
print(result)
```
这段代码使用了筛选法,最终输出了100以内的素数。