线性筛求质数
时间: 2024-02-15 14:06:17 浏览: 23
线性筛是一种快速求解素数的方法,具有时间复杂度 O(n) 的优点。其基本思想是:对于每个自然数 x,只需要用它最小的质因子筛掉其倍数,就可以得到一张素数表。
具体实现如下:
1. 初始化一个布尔数组 is_prime,表示每个数是否为素数,全部初始化为 true。
2. 初始化一个数组 primes,表示素数表,初始为空。
3. 从 2 开始遍历到 n,对于每个数 x:
- 如果 is_prime[x] 为 true,说明 x 是素数,将其加入 primes 数组。
- 对于 x 的每个质因子 p,将 is_prime[x * p] 标记为 false。
4. 遍历完毕后,primes 数组中存储的就是所有小于等于 n 的素数。
代码如下:
```python
def linear_sieve(n):
is_prime = [True] * (n + 1)
primes = []
for x in range(2, n + 1):
if is_prime[x]:
primes.append(x)
for p in primes:
if x * p > n:
break
is_prime[x * p] = False
if x % p == 0:
break
return primes
```
该算法的时间复杂度为 O(nloglogn),空间复杂度为 O(n)。