埃氏筛法优化,不再重复标记
时间: 2023-11-20 20:11:38 浏览: 24
埃氏筛法是一种常见的质数筛法,但是在实现中会存在重复标记的问题。为了解决这个问题,可以引入一个优化,即只标记每个合数一次。
具体实现方法是,对于每个质数p,从p^2开始标记其倍数,而不是从2p开始。因为对于每个小于p^2的数,其已经被之前的质数标记过了,所以只需要考虑大于等于p^2的数。
以下是代码实现:
```python
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(i * i, n + 1, i):
is_prime[j] = False
return primes
```
在以上代码中,我们只需要从p^2开始标记其倍数,即从i * i开始循环即可。这样可以避免重复标记的问题,提高效率。
相关问题
优化埃氏筛法,不再重复标记,并且打印出筛选次数和筛选后的数组
优化埃氏筛法的思路是,在标记质数时,只从当前质数的平方开始标记,因为在这之前的倍数已经被之前的质数标记过了。同时,我们可以使用一个数组记录每个数是否被标记过,避免重复标记。
以下是优化后的代码实现,同时输出了筛选次数和筛选后的数组:
```python
def prime_sieve(n):
is_prime = [True] * (n + 1)
primes = []
count = 0 # 记录筛选次数
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
count += 1
for j in range(i * i, n + 1, i):
is_prime[j] = False
print("筛选次数:", count)
print("筛选后的数组:", primes)
return primes
```
使用示例:
```python
>>> prime_sieve(30)
筛选次数: 10
筛选后的数组: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
埃氏筛法python
埃氏筛法(Sieve of Eratosthenes)是一种用于找出一定范围内所有素数的算法。它的基本思想是从2开始,将每个素数的倍数标记为合数,直到遍历完所有小于给定范围的数。以下是埃氏筛法的Python实现:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记数字是否为素数
is_prime = [True] * (n + 1)
is_prime = is_prime = False # 0和1不是素数
# 从2开始遍历到根号n
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# 将i的倍数标记为合数
for j in range(i * i, n + 1, i):
is_prime[j] = False
# 收集所有素数
primes = [i for i in range(n + 1) if is_prime[i]]
return primes
```
使用示例:
```python
n = 100
primes = sieve_of_eratosthenes(n)
print(primes)
```
这段代码将输出小于等于100的所有素数。