python 线性筛
时间: 2023-10-28 17:59:40 浏览: 64
Python线性筛法是一种用于找出一定范围内所有质数的算法。它的基本思想是通过筛除合数的方式来找出质数。具体步骤如下:
1. 首先,我们定义一个长度为N的布尔数组st,用来标记每个数是否为质数。
2. 初始化一个长度为N的空数组primes,用来存储找到的质数。
3. 从2开始遍历到N-1,如果当前数i不是合数(即st[i]为False),则将其加入primes数组,并将质数计数器cnt加1。
4. 对于每个质数primes[j],遍历范围为j从0到cnt-1,如果primes[j]乘以i超过了N,则跳出循环。
5. 在内层循环中,将合数primes[j]*i标记为True,同时判断i是否能整除primes[j],如果是则跳出内层循环。
6. 最后,输出质数的个数cnt。
以上就是Python线性筛法的基本原理和步骤。通过这种方法,我们可以高效地找出一定范围内的所有质数。
相关问题
线性筛求质数
线性筛是一种快速求解素数的方法,具有时间复杂度 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)。
素数python不同方法
有很多不同的方法可以用 Python 生成素数,以下是其中几个常见的方法:
1. 暴力枚举法:
这种方法的思路是从 2 开始遍历所有的自然数,判断其是否为素数。具体实现可以使用两个嵌套的循环,外层循环枚举自然数,内层循环用于判断是否为素数。代码示例:
```python
def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def generate_primes(n):
primes = []
for i in range(2, n):
if is_prime(i):
primes.append(i)
return primes
```
2. 厄拉多塞筛法:
这种方法的基本思路是从小到大枚举自然数,如果该数为素数,则将其所有的倍数都标记为合数。具体实现可以使用一个布尔数组来记录每个数是否为素数,初始时所有数都为素数,然后从 2 开始枚举,如果当前数为素数,则将其所有的倍数都标记为合数。代码示例:
```python
def generate_primes(n):
is_prime = [True] * n
primes = []
for i in range(2, n):
if is_prime[i]:
primes.append(i)
for j in range(i * i, n, i):
is_prime[j] = False
return primes
```
3. 线性筛法:
这种方法是一种优化过的厄拉多塞筛法,其基本思路是从小到大枚举自然数,如果该数为素数,则将其直接加入素数列表,并且将其所有的倍数都标记为合数。如果当前数是某个素数的倍数,则直接跳过。具体实现可以使用一个数组记录每个数的最小素因子,初始时所有数的最小素因子都为自身,然后从 2 开始枚举,如果当前数的最小素因子是自身,则将其加入素数列表,并将其所有的倍数的最小素因子都更新为该素数。代码示例:
```python
def generate_primes(n):
is_prime = [True] * n
primes = []
min_factors = [0] * n
for i in range(2, n):
if is_prime[i]:
primes.append(i)
min_factors[i] = i
for j in range(len(primes)):
if primes[j] > min_factors[i] or primes[j] * i >= n:
break
is_prime[primes[j] * i] = False
min_factors[primes[j] * i] = primes[j]
return primes
```
以上是三个常见的生成素数的方法,实际上还有很多其他的方法可以用于生成素数。