埃氏筛法的时间复杂度以及其的推导过程
时间: 2023-03-20 16:01:35 浏览: 302
埃氏筛法是一种用来找出小于等于某个数的所有素数的算法。其时间复杂度为 O(n log log n)。下面是其推导过程:
1. 首先生成一个从 2 到 n 的整数数组;
2. 从小到大遍历数组中的每个数,如果当前数是素数,则把数组中它的倍数标记为合数(即把它们标记为非素数);
3. 继续遍历下一个素数,重复步骤 2 直到遍历完所有小于等于 n 的素数。
对于第二步的标记操作,可以优化为只标记当前素数的平方及其之后的倍数,因为之前的倍数已经被之前的素数标记过了。这样可以减少不必要的操作,提高算法效率。
相关问题
埃拉托色尼筛法时间复杂度
埃拉托色尼筛法的时间复杂度是O(nlog(logn))。这是因为在该算法中,我们需要遍历从2到n的所有数字,并标记它们的倍数为合数。对于每个素数p,我们需要标记p的倍数,这样的操作需要进行n/p次。因此,总的操作次数可以近似为n/2 + n/3 + n/5 + ... + n/p,其中p为小于等于n的素数。根据数学推导,这个和的上界是nlog(logn)。因此,埃拉托色尼筛法的时间复杂度是O(nlog(logn))。
埃氏筛法与欧拉筛python
埃氏筛法:
```python
def Eratosthenes(n):
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n + 1: i] = [False] * len(primes[i * i: n + 1: i])
return [i for i in range(n + 1) if primes[i]]
```
欧拉筛:
```python
def Euler(n):
primes = []
is_prime = [True] * (n + 1)
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0:
break
return primes
```
两者的时间复杂度都是 $O(n \log \log n)$,但在常数上欧拉筛比埃氏筛法小,因此欧拉筛法更快。