编程筛子规律,即埃拉托斯特尼筛法(Sieve of Eratosthenes)的编程实现,可以按照以下步骤进行:
初始化布尔数组
创建一个布尔数组,长度为待筛数的范围(例如,从2到N)。
数组中的所有元素初始化为`True`,表示对应的数是素数。
遍历并筛选
从2开始遍历数组中的每一个数字。
如果当前数字是素数(即该位置上的值为`True`),则将该数的所有倍数(从2倍开始,每次增加该数本身)标记为`False`,因为它们不是素数。
输出结果
遍历完数组后,剩下的为`True`的数即为素数。
下面是一个Python实现的示例代码:
```python
def sieve_of_eratosthenes(n):
初始化布尔数组
is_prime = [True] * (n + 1)
is_prime = is_prime = False 0和1不是素数
遍历并筛选
for i in range(2, int(n0.5) + 1):
if is_prime[i]:
将i的所有倍数标记为False
for j in range(i * i, n + 1, i):
is_prime[j] = False
输出素数
primes = [i for i in range(2, n + 1) if is_prime[i]]
return primes
示例:找出100以内的所有素数
primes_up_to_100 = sieve_of_eratosthenes(100)
print(primes_up_to_100)
```
代码解释:
初始化
`is_prime = [True] * (n + 1)`:创建一个长度为`n+1`的布尔数组,初始值为`True`。
`is_prime = is_prime = False`:0和1不是素数,因此标记为`False`。
遍历和筛选
`for i in range(2, int(n 0.5) + 1)`:从2开始遍历到`sqrt(n)`,因为一个合数必定有一个小于等于其平方根的质因数。
`if is_prime[i]`:如果当前数字`i`是素数。
`for j in range(i * i, n + 1, i)`:将`i`的所有倍数标记为`False`。
输出结果
`primes = [i for i in range(2, n + 1) if is_prime[i]]`:遍历完数组后,剩下的为`True`的数即为素数。
这个算法的时间复杂度为`O(n log log n)`,空间复杂度为`O(n)`,是一种非常高效的素数筛选方法。