python素数筛法
时间: 2023-08-25 13:13:08 浏览: 64
素数筛法(Sieve of Eratosthenes)是一种用于找出一定范围内所有素数的算法。它的基本思想是从小到大依次遍历每个数字,将其倍数标记为非素数,最终剩下的未被标记的数字即为素数。
以下是使用Python实现素数筛法的示例代码:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1
相关问题
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,则跳出内层循环,避免重复标记。最后返回质数列表即可。
--相关问题--:
python欧拉筛法求素数
欧拉筛法是求解素数的一种高效算法,它的基本思想是通过筛去合数来得到素数。下面是Python实现欧拉筛法求素数的示例代码:
```python
def euler_sieve(n):
primes = []
is_prime = [True] * (n + 1)
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`,并将其全部初始化为`True`,表示在开始时所有的数都是素数。然后,我们从2开始遍历到`n`,如果当前这个数是素数,我们就把它加入到`primes`数组中,并且把它的倍数全部标记为合数(即将`is_prime[i * primes[j]]`置为`False`)。
最后,我们返回`primes`数组中的所有素数即可。