如何用python求100以内的素数？ _素数

素数是指只能被1和本身整除的正整数，比如2、3、5、7、11、13等。求100以内的素数是一个经典的问题，也是程序员入门时常见的练手题。下面我们将从多个角度分析如何用python求100以内的素数。
方法一：暴力枚举

最直接的想法是对每个数进行判断，看它是否能被1和本身以外的数整除。代码如下：
```python
for i in range(2, 101):
flag = True
for j in range(2, i):
if i % j == 0:
flag = False
break
if flag:
print(i)
```
这种方法的时间复杂度为O(n^2)，对于100以内的数来说还比较快。但如果我们要求更大范围内的素数，这种方法就变得相当低效了。
方法二：埃氏筛法
埃氏筛法是一种经典的素数筛法，可以在O(nloglogn)的时间复杂度内求出n以内的素数。其基本思想是：从2开始，将每个质数的倍数都标记成合数，直到筛完所有小于等于n的数。代码如下：
```python
def eratosthenes(n):
prime = [True] * (n + 1)
prime[0] = prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if prime[i]:
for j in range(i * i, n + 1, i):
prime[j] = False
return [i for i in range(n + 1) if prime[i]]
```
这段代码首先生成一个长度为n+1的布尔数组prime，其中prime[i]表示i是否为素数。然后从2开始，找到第一个素数p，将p的所有倍数都标记成合数，即prime[p*p], prime[p*p+p], prime[p*p+2p], ...都设为False 。接着找下一个素数，重复上述操作，直到筛完所有小于等于n的数。最后返回所有为素数的数。
方法三：欧拉筛法
欧拉筛法是一种优化的素数筛法，可以在O(n)的时间复杂度内求出n以内的素数。其基本思想是：对每个数只筛掉它最小的质因子，避免重复标记。代码如下：
```python
def euler(n):
prime = []
vis = [False] * (n + 1)
for i in range(2, n + 1):
if not vis[i]:
prime.append(i)
for j in range(len(prime)):
t = i * prime[j]
if t > n:
break
vis[t] = True
if i % prime[j] == 0:
break
return prime
```
这段代码首先生成一个空列表prime和一个长度为n+1的布尔数组vis，其中vis[i]表示i是否被筛掉了。接着从2开始遍历每个数，如果它没有被筛掉，说明它是素数，将其加入prime列表中。然后遍历prime列表中的每个质数，将当前数与质数的乘积标记成合数，同时判断如果当前数能被质数整除，就可以停止遍历质数列表了。
方法四：numpy优化
numpy是python中常用的数值计算库，它的数组操作比python原生的列表更快。我们可以用numpy数组来实现埃氏筛法，从而进一步提高效率。代码如下：
```python
import numpy as np
def eratosthenes_np(n):
prime = np.ones(n + 1, dtype=bool)
【如何用python求100以内的素数？】prime[0] = prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if prime[i]:
prime[i * i: n + 1: i] = False
return np.where(prime)[0]
```
这段代码首先生成一个长度为n+1的numpy布尔数组prime，其中prime[i]表示i是否为素数。然后从2开始，找到第一个素数p，将p的所有倍数都标记成合数，即prime[p*p:n+1:p]都设为False 。这里用到了numpy数组的切片和步长操作，可以一次性标记多个数。最后返回所有为素数的数。
方法五：多线程优化
我们可以用多线程来优化素数筛法，将筛数的任务分给多个线程同时处理，可以大大提高效率。代码如下：
```python
import threading
def eratosthenes_mt(n, num_threads=4):

如何用python求100以内的素数？

猜你喜欢