UDP广播协议叫吃饭

用户名：Mustenaka

访问量：149502

签　名：

个人博客www.mustenaka.cn

等　　级
排　　名	13
经　　验	25377
参赛次数	8
文章发表	197
年　　龄	3
在职情况	学生
学　　校	Sky_box
专　　业	NE

　　自我简介：

欢迎光临我的博客www.mustenaka.cn，Python，C#，U3D，C/C++开发合作可以找我

TA的其他文章

2664: 蓝桥杯2022年第十三届省赛真题-求和
浏览：679

Vector2 结构体模版 c++ 版本
浏览：55

你可能喜欢

Python求素数以及相关问题[朴素法][埃氏筛法][欧拉筛（线性筛）]

　　作者: UDP广播协议叫吃饭　　　　发表时间：2020-04-23 20:06:41 浏览：1036　|　评论：0　

# 求解素数的三种方法

------------
首先明白一下什么是素数，素数又名质数，除了2以外就是它本身只能拆分成1和自身相乘而的来的数，如7就是一个素数，他只能由1*7得到，而6不是一个素数，因为它既可以由1*6得到，也可以由2*3得到。

### 1.【朴素法】求解：
那么知道一个素数的概念，我们便有了一个最朴素的方法求解，即从2~n，每一个数i进行一个判断，这个数字i从2到i-1之间，是否存在一个数字可以与之求余=0的情况，如果没有，则这是一个素数。

```python
primesNumber = []

def is_prime(n):
    for i in range(2, n-1):
        if n % i == 0:
            return False
    return True

def primes(number):
    for i in range(2, number):
        if is_prime(i):
            primesNumber.append(i)

primes(10000)
print(primesNumber)
```
一个简单的优化就是，在筛选的时候将判断数据的上届使用sqrt开平方的方式简化判断数据，使用6这个数字就可以很好理解，sqrt(6)约等于2.4，取整后就是2，那么存在一个2*3=6可以满足，这与求完整的数据是一样的，只不过更加高效。

```python
primesNumber = []

def is_prime(n):
    for i in range(2, int(n ** 0.5)):
        if n % i == 0:
            return False
    return True

def primes(number):
    for i in range(2, number):
        if is_prime(i):
            primesNumber.append(i)
			
primes(20000)
print(primesNumber)
```

注：30000的时候会遇到Python的List存储超限的问题，导致无法全部存入

**朴素求法的时间复杂度是O(N^2)。**
此外，朴素方法一些变种可以间接性的增加处理速度，但基本上都是保持在这个复杂度了。

这里要注意一个Python的问题，我们采取List进行存放素数，然而Python的List的空间限制原因，导致我们求到大概3*10^4大小的数字的同时会发生一些溢出现象，这个时候是没有报错的，可以有两个解决的思路，这里就不帮助解决了（不然偏题）

1. List扩容，或者使用多段List（操作上没有那么方便）
2. 不存储素数，将所需要的数据直接输出

### 2.埃氏筛法
埃式筛法的思想是：对于不超过 n 的每个非负整数 p，删除 2*p, 3*p, 4*p,…，当处理完所有数之后，还没有被删除的就是素数。

> 我们可以从2开始，从小到大扫描每个数x,把x的倍数x*2,x*3,…x*(N/x)标记为非质数【此处其实可以优化，不用从2倍开始，因为对于每个数x,x的2倍，3倍都会被2,3，..<x的数筛过，因此只需从x倍开始】。

当扫描到一个数x时，若未被标记为非质数，那么该数便是质数，因为它能在比它小的数的过筛过程中逃过，就说明它前面没有一个数是它的倍数，然一个数的因子只可能比它小，因此我们可以断定，该数x便是一个素数。

一个简单的理解就是：利用倍数规则，将2的倍数，3的倍数，4的倍数，5的倍数等数字依次从素数表中删除，本质上是寻找非素数，但是总数-非素数=素数。

具体的代码如下：

```python
# 生成一个奇数序列
def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

# 筛选函数，保留不能整除的，筛掉可以整除的，即倍数。
def _not_divisible(n):
    return lambda x: x % n > 0

# 求素数函数。
def primes():
    yield 2
    it = _odd_iter()  # 初始序列
    while True:
        n = next(it)
        yield n
        it = filter(_not_divisible(n), it)  # it在不断的next调用中，进行筛选。

# 输出100000以内的所有素数,速度稍微快一丢丢：
for n in primes():
    if n < 100000:
        print(n, end=' ')
    else:
        break
```
> 这份代码采取利用生成器——filter()筛选函数进行过滤，这样写比较直观而且filter过滤的速度相当快，但如果基础不是很好可以参考一下这个C语言版本的，较为容易理解。

```cpp
    bool isprime[10000005];
    void aishiPrime(int n){
	memset(isprime,true,sizeof(isprime));
	isprime[1]=false;
	for (int i=2; i*i<=n; i++){
		if (isprime[i])	{    
		  	for(int j=i*i;j<=n; j+=i) 
            	            isprime[j]=false; 
    	        }
	}	    
    }
```
**埃氏筛法的时间复杂度为：O(n*logn)**

### 3.欧拉筛（线性筛）
欧拉筛的思想是：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

> 合数：【摘自百度百科】合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。最小的合数是4。其中，完全数与相亲数是以它为基础的。

如：385这个数，385= 5 * 7* 11，会被5的倍数时标记一次，7的倍数时标记一次，11的倍数时标记一次，造成效率达不到最优。而线性筛法基于改进这个不足的基础上，在线性时间内，也就是O(n)，用筛选的方法把素数找出来。

(从网上盗来的图2333333)
![](/image_editor_upload/20200423080433_85613.png)
代码如下为：

```python
#欧拉筛选--线性筛
# 返回小于r的素数列表
def oula(r):
    # 全部初始化为0
    prime = [0 for i in range(r+1)]
    # 存放素数
    common = []
    for i in range(2, r+1):
        if prime[i] == 0:
            common.append(i)
        for j in common:
            if i*j > r:
                break
            prime[i*j] = 1
            #将重复筛选剔除
            if i % j == 0:
                break
    return common

prime = oula(20000)
print(prime)
```
**欧拉筛的时间复杂度为O(n)**

从时间的运行上相对而言，素数的筛选，最理想的还是欧拉筛，但是需要在前文理解的基础上才能够很好的写出来。
感觉这篇文章类似的有很多人发表过了，就凑巧发一篇Python版本的吧，比较最近一直在用Python做事情.
全文转载自本人博客：http://www.mustenaka.cn/index.php/2020/04/23/primenumbersinpython/
目前只在C语言网和本人博客中发表。

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

【数组的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

拆分位数（C语言代码）

简单的a+b （C语言代码）

【亲和数】（C语言代码）

Python求素数以及相关问题[朴素法][埃氏筛法][欧拉筛（线性筛）]

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

完数（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

矩形面积交（C语言代码）

1134题解(求分析)

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

【数组的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

拆分位数 （C语言代码）

简单的a+b （C语言代码）

【亲和数】 （C语言代码）

Python求素数以及相关问题[朴素法][埃氏筛法][欧拉筛（线性筛）]

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

完数 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

矩形面积交 （C语言代码）

1134题解(求分析)

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

【数组的距离】（C语言代码）

拆分位数（C语言代码）

【亲和数】（C语言代码）

　　评论区

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

完数（C语言代码）

矩形面积交（C语言代码）

母牛的故事（C语言代码）