欧拉筛法筛选素数,不重复标记 python
时间: 2024-02-26 09:26:19 浏览: 30
以下是欧拉筛法筛选素数,不重复标记的Python代码:
```python
def eratosthenes(n):
is_prime = [True] * (n+1)
primes = []
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
for j in range(len(primes)):
if i * primes[j] > n:
break
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
break
return primes
```
该算法使用is_prime列表来记录每个数是否为素数,初始时所有数都被标记为素数。然后从2开始遍历每个数,如果该数是素数,则将其加入primes列表中,并将其倍数标记为非素数。在将倍数标记为非素数时,可以通过判断当前数和当前素数的乘积是否大于n来提前退出循环,避免不必要的计算。如果当前数能够被某个素数整除,则跳出当前循环,因为该数已经被标记过了。最后返回primes列表即可。
相关问题
欧拉筛法求素数python
可以使用以下代码实现欧拉筛法求素数:
```python
def primes(n):
is_prime = [True] * (n+1)
prime_list = []
for i in range(2, n+1):
if is_prime[i]:
prime_list.append(i)
j = 0
while j < len(prime_list) and i * prime_list[j] <= n:
is_prime[i * prime_list[j]] = False
if i % prime_list[j] == 0:
break
j += 1
return prime_list
```
其中,is_prime 是一个数组,用来记录每个数是否为素数。我们从 2 开始,依次判断每个数是否为素数,如果是素数,就将其加入 prime_list 中,并将其倍数标记为非素数。在标记倍数的过程中,我们只需要遍历当前已知的素数,因为其他数已经被标记过了。
Python欧拉筛法求素数
Python欧拉筛法求素数的代码如下:
```python
def euler_sieve(n):
is_prime = [True] * (n+1)
prime_list = []
for i in range(2, n+1):
if is_prime[i]:
prime_list.append(i)
for j in range(len(prime_list)):
if i * prime_list[j] > n:
break
is_prime[i * prime_list[j]] = False
if i % prime_list[j] == 0:
break
return prime_list
`
这个算法的时间复杂度为O(n),空间复杂度为O(n)。它的基本思路是先将所有数标记为质数,然后从2开始遍历到n,如果当前数是质数,则将它的倍数标记为合数。具体实现时,可以用一个布尔数组is_prime来记录每个数是否为质数,用一个列表prime_list来记录已经筛选出来的质数。在遍历到一个质数i时,将它的倍数i*j(j为质数列表中的元素)标记为合数,并且如果i能够整除j,则跳出内层循环,避免重复标记。最后返回质数列表即可。
--相关问题--:
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)